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.
Author: | André Gaul, Martin H. Gutknecht, Jörg Liesen, Reinhard Nabben |
---|---|
URN: | urn:nbn:de:0296-matheon-7491 |
Referee: | Peter Deuflhard |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2011/01/28 |
Release Date: | 2011/01/26 |
Tag: | CG; GMRES; Krylov subspace methods; MINRES; augmentation; deflation; subspace recycling |
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 |