A framework for deflated and augmented Krylov subspace methods

Abstract

We consider deflation and augmentation techniques for accelerating the convergence of Krylov subspace methods for the solution of nonsingular linear algebraic systems. Despite some formal similarity, the two techniques are conceptually different from preconditioning. Deflation (in the sense the term is used here) "removes" certain parts from the operator making it singular, while augmentation adds a subspace to the Krylov subspace (often the one that is generated by the singular operator); in contrast, preconditioning changes the spectrum of the operator without making it singular. Deflation and augmentation have been used in a variety of methods and settings. Typically, deflation is combined with augmentation to compensate for the singularity of the operator, but both techniques can be applied separately. We introduce a framework of Krylov subspace methods that satisfy a Galerkin condition. It includes the families of orthogonal residual (OR) and minimal residual (MR) methods. We show that in this framework augmentation can be achieved either explicitly or, equivalently, implicitly by projecting the residuals appropriately and correcting the approximate solutions in a final step. We study conditions for a breakdown of the deflated methods, and we show several possibilities to avoid such breakdowns for the deflated MINRES method. Numerical experiments illustrate properties of different variants of deflated MINRES analyzed in this paper.

24 pages, 3 figures

References in corpus (1)

• Deflated GMRES for Systems with Multiple Shifts and Multiple Right-Hand Sides

Cited by in corpus (9)

• Block Krylov subspace recycling for shifted systems with unrelated right-hand sides
• GMRES algorithms over 35 years
• Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
• A flexible and adaptive Simpler GMRES with deflated restarting for shifted linear systems
• Deflation-accelerated preconditioning of the Poisson-Neumann Schur problem on long domains with a high-order discontinuous element-based collocation method
• Accelerating linear system solvers for time domain component separation of cosmic microwave background data
• Deflation for the off-diagonal block in symmetric saddle point systems
• Absorption kinetics of vacancies by cavities in Aluminum: numerical characterization of sink strengths and first-passage statistics through Krylov subspace projection and eigenvalue deflation
• Two-level Nyström--Schur preconditioner for sparse symmetric positive definite matrices