Volume 14, pp. 1-19, 2002.

Superlinear CG convergence for special right-hand sides

Bernhard Beckermann and Arno B. J. Kuijlaars

Abstract

Recently, we gave a theoretical explanation for superlinear convergence behavior observed while solving large symmetric systems of equations using the Conjugate Gradient method. Roughly speaking, one may observe superlinear convergence while solving a sequence of (symmetric positive definite) linear systems if the asymptotic eigenvalue distribution of the sequence of the corresponding matrices of coefficients is far from an equilibrium distribution. However, it is well known that the convergence of the Conjugate Gradient or other Krylov subspace methods does not only depend on the spectrum but also on the right-hand side of the underlying system and the starting vector. In this paper we present a family of examples based on the discretization via finite differences of the one dimensional Poisson problem where the asymptotic distribution equals an equilibrium distribution but one may as well observe superlinear convergence according to the particular choice of the right-hand sides. Our findings are related to some recent results concerning asymptotics of discrete orthogonal polynomials. An important tool in our investigations is a constrained energy problem in logarithmic potential theory, where an additional external field is used being related to our particular right-hand sides.

Full Text (PDF) [410 KB], BibTeX

Key words

Superlinear convergence, Conjugate gradients, Krylov subspace methods, Logarithmic potential theory.

AMS subject classifications

65F10, 65E05, 31A99, 41A10.

ETNA articles which cite this article

Vol. 20 (2005), pp. 180-197 Jörg Liesen and Petr Tichý: On the worst-case convergence of MR and CG for symmetric positive definite tridiagonal Toeplitz matrices

Vol. 58 (2023), pp. 115-135 Christian E. Schaerer, Daniel B. Szyld, and Pedro J. Torres: A posteriori superlinear convergence bounds for block conjugate gradient

< Back