A framework for deflated and augmented Krylov subspace methods
From MaRDI portal
Publication:2848622
DOI10.1137/110820713zbMATH Open1273.65049arXiv1206.1506OpenAlexW3098036980MaRDI QIDQ2848622FDOQ2848622
André Gaul, Martin H. Gutknecht, Reinhard Nabben, Jörg Liesen
Publication date: 26 September 2013
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1206.1506
Recommendations
- Deflated and Augmented Krylov Subspace Techniques
- Deflated Krylov subspace methods for nearly singular linear systems
- Deflated and augmented Krylov subspace methods: A framework for deflated BiCG and related solvers
- Deflation and Balancing Preconditioners for Krylov Subspace Methods Applied to Nonsymmetric Matrices
- Analysis of Augmented Krylov Subspace Methods
Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10)
Cited In (49)
- Deflated Krylov subspace methods for nearly singular linear systems
- A framework for studying the regularizing properties of Krylov subspace methods
- A flexible and adaptive simpler block GMRES with deflated restarting for linear systems with multiple right-hand sides
- A Robust Iterative Scheme for Symmetric Indefinite Systems
- Two-Level Nyström--Schur Preconditioner for Sparse Symmetric Positive Definite Matrices
- A new projected variant of the deflated block conjugate gradient method
- A quasi-minimal residual variant of the BiCORSTAB method for nonsymmetric linear systems
- A dynamically deflated GMRES adjoint solver for aerodynamic shape optimization
- Projections, Deflation, and Multigrid for Nonsymmetric Matrices
- A transpose-free quasi-minimal residual variant of the CORS method for solving non-Hermitian linear systems
- Deflated and restarted Krylov subspace methods for Sylvester tensor equations
- Numerical solution of singular Sylvester equations
- Absorption kinetics of vacancies by cavities in aluminum: numerical characterization of sink strengths and first-passage statistics through Krylov subspace projection and eigenvalue deflation
- A new quasi-minimal residual method based on a biconjugate \(A\)-orthonormalization procedure and coupled two-term recurrences
- Acceleration of implicit schemes for large linear systems of differential-algebraic equations
- A breakdown-free block conjugate gradient method
- Deflated Krylov Iterations in Domain Decomposition Methods
- A new preconditioner update strategy for the solution of sequences of linear systems in structural mechanics: application to saddle point problems in elasticity
- Conjugate direction methods for multiple solution of SLAEs
- Deflation for the Off-Diagonal Block in Symmetric Saddle Point Systems
- On restarted and deflated block FOM and GMRES methods for sequences of shifted linear systems
- Augmented and deflated CMRH method for solving nonsymmetric linear systems
- A flexible and adaptive simpler GMRES with deflated restarting for shifted linear systems
- A note on augmented unprojected Krylov subspace methods
- New convergence analysis of GMRES with weighted norms, preconditioning, and deflation, leading to a new deflation space
- A survey of subspace recycling iterative methods
- Automatic Exploration Techniques of Numerical Bifurcation Diagrams Illustrated by the Ginzburg--Landau Equation
- Preconditioners for Krylov subspace methods: An overview
- Deflated and augmented global Krylov subspace methods for the matrix equations
- A hybridized iterative algorithm of the BiCORSTAB and GPBiCOR methods for solving non-Hermitian linear systems
- Deflation-accelerated preconditioning of the Poisson-Neumann Schur problem on long domains with a high-order discontinuous element-based collocation method
- Some iterative approaches for Sylvester tensor equations. I: A tensor format of truncated loose simpler GMRES
- Iterative preconditioned methods in Krylov spaces: trends of the 21st century
- On the residual norms, the Ritz values and the harmonic Ritz values that can be generated by restarted GMRES
- Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics
- An accelerated subspaces recycling strategy for the deflation of parametric linear systems based on model order reduction
- A Domain Decomposition Rayleigh--Ritz Algorithm for Symmetric Generalized Eigenvalue Problems
- Pseudoeigenvector bases and deflated GMRES for highly nonnormal matrices
- Accelerating the solution of linear systems appearing in two-phase reservoir simulation by the use of POD-based deflation methods
- The deflated conjugate gradient method: convergence, perturbation and accuracy
- Randomized flexible GMRES with deflated restarting
- On the Spectrum of Deflated Matrices with Applications to the Deflated Shifted Laplace Preconditioner for the Helmholtz Equation
- On applying deflation and flexible preconditioning to the adaptive simpler GMRES method for Sylvester tensor equations
- GMRES with multiple preconditioners
- Block conjugate gradient algorithms for least squares problems
- GMRES algorithms over 35 years
- Mstab: Stabilized Induced Dimension Reduction for Krylov Subspace Recycling
- Subspace Recycling--Based Regularization Methods
- An Adaptive MultiPreconditioned Conjugate Gradient Algorithm
This page was built for publication: A framework for deflated and augmented Krylov subspace methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848622)
