ISSN:
1572-9265
Keywords:
Circulant matrices
;
conjugate gradient
;
preconditioner
;
Toeplitz matrices
;
AMS(MOS) 65F10
;
65F15
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper we introduce a new preconditioner for banded Toeplitz matrices, whose inverse is itself a Toeplitz matrix. Given a banded Hermitian positive definite Toeplitz matrixT, we construct a Toepliz matrixM such that the spectrum ofMT is clustered around one; specifically, if the bandwidth ofT is β, all but β eigenvalues ofMT are exactly one. Thus the preconditioned conjugate gradient method converges in β+1 steps which is about half the iterations as required by other preconditioners for Toepliz systems that have been suggested in the literature. This idea has a natural extension to non-banded and non-Hermitian Toeplitz matrices, and to block Toeplitz matrices with Toeplitz blocks which arise in many two dimensional applications in signal processing. Convergence results are given for each scheme, as well as numerical experiments illustrating the good convergence properties of the new preconditioner.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02140682
Permalink
