Deflated and augmented Krylov subspace methods: Basic Facts and a Breakdown-free deflated MINRES

Please always quote using this URN: urn:nbn:de:0296-matheon-7491
  • In this paper we consider deflation and augmentation techniques for accelerating the convergence of Krylov subspace methods for the solution of nonsingular linear algebraic systems. The two techniques are conceptually different from preconditioning. Deflation "removes" certain parts from the operator, while augmentation adds a subspace to the Krylov subspace. Both approaches have been used in a variety of methods and settings. For Krylov subspace methods that satisfy a (Petrov-) Galerkin condition we show that augmentation can in general be achieved implicitly by projecting the residuals appropriately and correcting the approximate solutions in a final step. In this context, we analyze known methods to deflate CG, GMRes and MinRes. Our analysis reveals that the recently proposed RMinRes method can break down. We show how such breakdowns can be avoided by choosing a special initial guess, and we derive a breakdown-free deflated MinRes method. In numerical experiments we study the properties of different variants of MinRes analyzed in this paper.

Download full text files

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:André Gaul, Martin H. Gutknecht, Jörg Liesen, Reinhard Nabben
URN:urn:nbn:de:0296-matheon-7491
Referee:Peter Deuflhard
Language:English
Date of first Publication:2011/01/28
MSC-Classification:65-XX NUMERICAL ANALYSIS / 65Fxx Numerical linear algebra / 65F08 Preconditioners for iterative methods
65-XX NUMERICAL ANALYSIS / 65Fxx Numerical linear algebra / 65F10 Iterative methods for linear systems [See also 65N22]
Preprint Number:759