We propose a new embedding method to deduce preconditioners for Hermitian positive definite (HPD) Toeplitz matrices A_n, and the solutions of HPD A_n x_n = b_n have been studied by the preconditioned conjugate gradient method(PCGM). We finally prove that under the Wiener class assumption, the preconditioned Toeplitz systems will have a clustered spectrum and the PCGM converges in a finite number of iterations independent of n so that the computational complexity for solving these Toeplitz systems is O(nlogn). This new method can be considered as a generalized one and many former methods have been proved as just its special cases. We have also demonstrated some applications.

Footnotes:

¹ Joint work with JinShun MEI and YouMing LI.