Spectral deflation in Krylov solvers: A theory of coordinate space based methods
Abstract
For the iterative solution of large sparse linear systems we develop a theory for a family of augmented and deflated Krylov space solvers that are coordinate based in the sense that the given problem is transformed into one that is formulated in terms of the coordinates with respect to the augmented bases of the Krylov subspaces. Except for the augmentation, the basis is as usual generated by an Arnoldi or Lanczos process, but now with a deflated, singular matrix. The idea behind deflation is to explicitly annihilate certain eigenvalues of the system matrix, typically eigenvalues of small absolute value. The deflation of the matrix is based on an either orthogonal or oblique projection on a subspace that is complimentary to the deflated approximately invariant subspace. While an orthogonal projection allows us to find minimal residual norm solutions, the oblique projections, which we favor when the matrix is non-Hermitian, allow us in the case of an exactly invariant subspace to correctly deflate both the right and the corresponding left (possibly generalized) eigenspaces of the matrix, so that convergence only depends on the non-deflated eigenspaces. The minimality of the residual is replaced by the minimality of a quasi-residual. Among the methods that we treat are primarily deflated versions of GMRes, MinRes, and QMR, but we also extend our approach to deflated, coordinate space based versions of other Krylov space methods including variants of CG and BiCG. Numerical results will be published elsewhere. Show more
Publication status
publishedExternal links
Journal / series
SAM Research ReportVolume
Publisher
Seminar for Applied Mathematics, ETH ZurichSubject
Linear equations; Krylov space method; Krylov subspace method; Deflation; Augmented basis; Recycling Krylov subspaces; (singular) preconditioning; GMRES; MinRes; QMR; CG; BiCGOrganisational unit
03435 - Schwab, Christoph / Schwab, Christoph
More
Show all metadata
ETH Bibliography
yes
Altmetrics