Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Superlinear PCG methods for symmetric Toeplitz systems

Author: Stefano Serra
Journal: Math. Comp. 68 (1999), 793-803
MSC (1991): Primary 65F10, 65F15
MathSciNet review: 1620251
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we deal with the solution, by means of preconditioned conjugate gradient (PCG) methods, of $n\times n$ symmetric Toeplitz systems $A_n(f) \mathbf { x}= \mathbf { b}$ with nonnegative generating function $f$. Here the function $f$ is assumed to be continuous and strictly positive, or is assumed to have isolated zeros of even order. In the first case we use as preconditioner the natural and the optimal $\tau$ approximation of $A_n(f)$ proposed by Bini and Di Benedetto, and we prove that the related PCG method has a superlinear rate of convergence and a total arithmetic cost of $O(n\log n)$ ops. Under the second hypothesis we cannot guarantee that the natural $\tau$ matrix is positive definite, while for the optimal we show that, in the ill-conditioned case, this can be really a bad choice. Consequently, we define a new $\tau$ matrix for preconditioning the given system; then, by applying the Sherman–Morrison–Woodbury inversion formula to the preconditioned system, we introduce a small, constant number of subsidiary systems which can be solved again by means of the previous PCG method. Finally, we perform some numerical experiments that show the effectiveness of the devised technique and the adherence with the theoretical analysis.

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, Corso Italia 40, 56100 Pisa (ITALY)
MR Author ID: 332436

Keywords: Toeplitz matrix, $\tau$ algebra, conjugate gradient method
Received by editor(s): February 7, 1996
Received by editor(s) in revised form: October 15, 1996, and July 18, 1997
Article copyright: © Copyright 1999 American Mathematical Society