Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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 Free Access

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

DOI: http://dx.doi.org/10.1090/S0025-5718-1993-1195423-4
PII: S 0025-5718(1993)1195423-4
Keywords: Toeplitz matrix, circulant matrix, generating function, preconditioned conjugate gradient method, superlinear convergence rate
Article copyright: © Copyright 1993 American Mathematical Society