Circulant preconditioners for complex Toeplitz matrices

Raymond H. CHAN*, Man Chung YEUNG

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

20 Citations (Scopus)


The solution of n-by-n complex Toeplitz systems Anx = b by the preconditioned conjugate gradient method is studied. The preconditioner Cn is the circulant matrix that minimizes ||Bn-An||F over all circulant matrices Bn. The authors prove that if the generating function of An is a -periodic continuous complex-valued function without any zeros, then the spectrum of the normalized preconditioned matrix (Cn-1An)*(Cn-1An) will be clustered around one. Hence they show that if the condition number of An is of (nα), the conjugate gradient method, when applied to solving the normalized preconditioned system, converges in at most (α log n+1) steps. Thus the total complexity of the algorithm is (αn log2 n + 1 log n).

Original languageEnglish
Pages (from-to)1193-1207
Number of pages15
JournalSIAM Journal on Numerical Analysis
Issue number4
Publication statusPublished - Aug 1993
Externally publishedYes


  • Toeplitz matrix
  • circulant matrix
  • preconditioned conjugate gradient method
  • generating function


Dive into the research topics of 'Circulant preconditioners for complex Toeplitz matrices'. Together they form a unique fingerprint.

Cite this