Circulant preconditioners for toeplitz matrices with piecewise continuous generating functions

Man Chung YEUNG, Hon Fu Raymond CHAN

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

10 Citations (Scopus)


We consider the solution of -by- Toeplitz systems T„x = b by preconditioned conjugate gradient methods. The preconditioner Cn is the T. Chan circulant preconditioner, which is defined to be the circulant matrix that minimizes B„ - T„fover all circulant matrices B„ . For Toeplitz matrices generated by positive In -periodic continuous functions, we have shown earlier that the spectrum of the preconditioned system C„Tn is clustered around 1 and hence the convergence rate of the preconditioned system is superlinear. However, in this paper, we show that if instead the generating function is only piecewise continuous, then for all e sufficiently small, there are 0(log) eigenvalues of Cñ ’ T„ that lie outside the interval (1 —e , 1 + e). In particular, the spectrum of Cñ ’ Tn cannot be clustered around 1. Numerical examples are given to verify that the convergence rate of the method is no longer superlinear in general.

Original languageEnglish
Pages (from-to)701-718
Number of pages18
JournalMathematics of Computation
Issue number204
Publication statusPublished - Oct 1993
Externally publishedYes


  • Circulant matrix
  • Generating function
  • Preconditioned conjugate gradient method
  • Superlinear convergence rate
  • Toeplitz matrix


Dive into the research topics of 'Circulant preconditioners for toeplitz matrices with piecewise continuous generating functions'. Together they form a unique fingerprint.

Cite this