Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2024 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Superlinear PCG methods for symmetric Toeplitz systems
HTML articles powered by AMS MathViewer

by Stefano Serra PDF
Math. Comp. 68 (1999), 793-803 Request permission

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
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
  • Email: serra@mail.dm.unipi.it
  • Received by editor(s): February 7, 1996
  • Received by editor(s) in revised form: October 15, 1996, and July 18, 1997
  • © Copyright 1999 American Mathematical Society
  • Journal: Math. Comp. 68 (1999), 793-803
  • MSC (1991): Primary 65F10, 65F15
  • DOI: https://doi.org/10.1090/S0025-5718-99-01045-5
  • MathSciNet review: 1620251