Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems

Raymond H. CHAN, Ping Tak Peter TANG

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


This paper considers the solutions of Hermitian Toeplitz systems where the Toeplitz matrices are generated by nonnegative functions ƒ. The preconditioned conjugate gradient method withwell-known circulant preconditioners fails in the case when ƒ has zeros. This paper employs Toeplitz matrices offixed bandwidth as preconditioners. Their generating functions g are trigonometric polynomials of fixed degree and aredetermined by minimizing the maximum relative error ||(ƒ - g)/ƒ||∞. Itis shown that the condition number of systems preconditioned by theband-Toeplitz matrices are O(1) for ƒ, with or withoutzeros. When ƒ is positive, the preconditioned systems converge at thesame rate as other well-known circulant preconditioned systems. An a prioribound of the number of iterations required for convergence is also given.
Original languageEnglish
Pages (from-to)164-171
Number of pages8
JournalSIAM Journal on Scientific Computing
Issue number1
Publication statusPublished - Jan 1994
Externally publishedYes


  • Toeplitz matrix
  • generating function
  • preconditioned conjugate gradient method
  • Chebyshev approximation
  • Remez algorithm


Dive into the research topics of 'Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems'. Together they form a unique fingerprint.

Cite this