Fast Iterative Solvers for Toeplitz-Plus-Band Systems

Raymond H. CHAN, Kwok-Po NG

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


The authors consider the solutions of Hermitian Toeplitz-plus-band systems (An + Bn)x = b, where An are n-by-n Toeplitz matrices and Bn are n-by-n band matrices with bandwidth independent of n. These systems appear in solving integrodifferential equations and signal processing. However, unlike the case of Toeplitz systems, no fast direct solvers have been developed for solving them. In this paper, the preconditioned conjugate gradient method with band matrices as preconditioners is used. The authors prove that if An is generated by a nonnegative piecewise continuous function and Bn is positive semidefinite, then there exists a band matrix Cn, with bandwidth independent of n, such that the spectra of Cn-1 (An + Bn) are uniformly bounded by a constant independent of n. In particular, we show that the solution of (An + Bn)x = b can be obtained in O(n log n) operations.
Original languageEnglish
Pages (from-to)1013-1019
Number of pages7
JournalSIAM Journal on Scientific Computing
Issue number5
Publication statusPublished - Sept 1993
Externally publishedYes


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


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

Cite this