Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems

Author: Stefano Serra
Journal: Math. Comp. 66 (1997), 651-665
MSC (1991): Primary 65F10, 65F15
MathSciNet review: 1401945
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we are concerned with the solution of $n\times n$ Hermitian Toeplitz systems with nonnegative generating functions $f$. The preconditioned conjugate gradient (PCG) method with the well-known circulant preconditioners fails in the case where $f$ has zeros. In this paper we consider as preconditioners band-Toeplitz matrices generated by trigonometric polynomials $g$ of fixed degree $l$. We use different strategies of approximation of $f$ to devise a polynomial $g$ which has some analytical properties of $f$, is easily computable and is such that the corresponding preconditioned system has a condition number bounded by a constant independent of $n$. For each strategy we analyze the cost per iteration and the number of iterations required for the convergence within a preassigned accuracy. We obtain different estimates of $l$ for which the total cost of the proposed PCG methods is optimal and the related rates of convergence are superlinear. Finally, for the most economical strategy, we perform various numerical experiments which fully confirm the effectiveness of approximation theory tools in the solution of this kind of linear algebra problems.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (1991): 65F10, 65F15

Retrieve articles in all journals with MSC (1991): 65F10, 65F15

Additional Information

Stefano Serra
Affiliation: Dipartimento di Informatica, Università di Pisa, Corso Italia 40, 56100 Pisa (Italy)

Keywords: Toeplitz matrix, Chebyshev interpolation and approximation, conjugate gradient method, Remez algorithm
Received by editor(s): January 20, 1995
Received by editor(s) in revised form: January 26, 1996
Article copyright: © Copyright 1997 American Mathematical Society