TOEPLITZ EQUATIONS BY CONJUGATE GRADIENTS WITH CIRCULANT PRECONDITIONER

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)104-119
Journal / PublicationSIAM Journal on Scientific Computing
Volume10
Issue number1
Publication statusPublished - Jan 1989
Externally publishedYes

Abstract

This paper studies the solution of symmetric positive definite Toeplitz systems Ax b by the preconditioned conjugate gradient method. The preconditioner is a circulant matrix C that copies the middle diagonals of A, and each iteration uses the Fast Fourier Transform. Convergence is governed by the eigenvalues of C-1 A-a Toeplitz-circulant eigenvalue problem-and it is fast if those eigenvalues are clustered. The limiting behavior of the eigenvalues is found as the dimension increases, and it is proved that they cluster around ℷ = 1. For a wide class of problems the error after q conjugate gradient steps decreases as rq2.

Research Area(s)

  • Toeplitz, circulant, conjugate gradient, Hankel