Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions

Authors: Man-Chung Yeung and Raymond H. Chan
Journal: Math. Comp. 61 (1993), 701-718
MSC: Primary 65F35
MathSciNet review: 1195423
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider the solution of n-by-n Toeplitz systems $ {T_n}x = b$ by preconditioned conjugate gradient methods. The preconditioner $ {C_n}$ is the T. Chan circulant preconditioner, which is defined to be the circulant matrix that minimizes $ {\left\Vert {{B_n} - {T_n}} \right\Vert _F}$ over all circulant matrices $ {B_n}$. For Toeplitz matrices generated by positive $ 2\pi $-periodic continuous functions, we have shown earlier that the spectrum of the preconditioned system $ C_n^{ - 1}{T_n}$ is clustered around 1 and hence the convergence rate of the preconditioned system is superlinear. However, in this paper, we show that if instead the generating function is only piecewise continuous, then for all $ \varepsilon $ sufficiently small, there are $ O(\log n)$ eigenvalues of $ C_n^{ - 1}{T_n}$ that lie outside the interval $ (1 - \varepsilon,1 + \varepsilon)$. In particular, the spectrum of $ C_n^{ - 1}{T_n}$ cannot be clustered around 1. Numerical examples are given to verify that the convergence rate of the method is no longer superlinear in general.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F35

Retrieve articles in all journals with MSC: 65F35

Additional Information

Keywords: Toeplitz matrix, circulant matrix, generating function, preconditioned conjugate gradient method, superlinear convergence rate
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society