Conjugate gradient methods for Toeplitz systems

Raymond H. CHAN*, Michael K. NG

*Corresponding author for this work

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

673 Citations (Scopus)

Abstract

In this expository paper, we survey some of the latest developments in using preconditioned conjugate gradient methods for solving Toeplitz systems. One of the main results is that the complexity of solving a large class of n-by-n Toeplitz systems is reduced to O(n log n) operations as compared to O(n log2 n) operations required by fast direct Toeplitz solvers. Different preconditioners proposed for Toeplitz systems are reviewed. Applications to Toeplitz-related systems arising from partial differential equations, queueing networks, signal and image processing, integral equations, and time series analysis are given.

Original languageEnglish
Pages (from-to)427-482
Number of pages56
JournalSIAM Review
Volume38
Issue number3
DOIs
Publication statusPublished - Sept 1996
Externally publishedYes

Keywords

  • Differential equations
  • Integral equations
  • Preconditioned conjugate gradient methods
  • Preconditioners
  • Queueing problems
  • Signal and image processing
  • Time series
  • Toeplitz matrices

Fingerprint

Dive into the research topics of 'Conjugate gradient methods for Toeplitz systems'. Together they form a unique fingerprint.

Cite this