Toeplitz preconditioners for Hermitian Toeplitz systems

Raymond H. CHAN*, Kwok Po NG

*Corresponding author for this work

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

66 Citations (Scopus)


We propose a new type of preconditioners for Hermitian positive definite Toeplitz systems Anx = b where An are assumed to be generated by functions f that are positive and 2π-periodic. Our approach is to precondition Ãn by the Toeplitz matrix Ãn generated by 1/f. We prove that the resulting preconditioned matrix ÃnAn will have clustered spectrum. When Ãn cannot be formed efficiently, we use quadrature rules and convolution products to construct nearby approximations to Ãn. We show that the resulting approximations are Toeplitz matrices which can be written as sums of {ω}-circulant matrices. As a side result, we prove that any Toeplitz matrix can be written as a sum of {ω}-circulant matrices. We then show that our Toeplitz preconditioners Tn are generalizations of circulant preconditioners and the way they are constructed is similar to the approach used in the additive Schwarz method for elliptic problems. We finally prove that the preconditioned systems TnAn will have clustered spectra around 1.

Original languageEnglish
Pages (from-to)181-208
Number of pages28
JournalLinear Algebra and Its Applications
Publication statusPublished - 1 Sept 1993
Externally publishedYes


Dive into the research topics of 'Toeplitz preconditioners for Hermitian Toeplitz systems'. Together they form a unique fingerprint.

Cite this