The deflated conjugate gradient method: convergence, perturbation and accuracy
From MaRDI portal
Publication:501271
Abstract: Deflation techniques for Krylov subspace methods have seen a lot of attention in recent years. They provide means to improve the convergence speed of these methods by enriching the Krylov subspace with a deflation subspace. The most common approach for the construction of deflation subspaces is to use (approximate) eigenvectors, but also more general subspaces are applicable. In this paper we discuss two results concerning the accuracy requirements within the deflated CG method. First we show that the effective condition number which bounds the convergence rate of the deflated conjugate gradient method depends asymptotically linearly on the size of the perturbations in the deflation subspace. Second, we discuss the accuracy required in calculating the deflating projection. This is crucial concerning the overall convergence of the method, and also allows to save some computational work. To show these results, we use the fact that as a projection approach deflation has many similarities to multigrid methods. In particular, recent results relate the spectra of the deflated matrix to the spectra of the error propagator of twogrid methods. In the spirit of these results we show that the effective condition number can be bounded by the constant of a weak approximation property.
Recommendations
- Projections, deflation, and multigrid for nonsymmetric matrices
- A framework for deflated and augmented Krylov subspace methods
- On the use of deflation to improve the convergence of conjugate gradient iteration
- Deflated and Augmented Krylov Subspace Techniques
- On the spectrum of deflated matrices with applications to the deflated shifted Laplace preconditioner for the Helmholtz equation
Cites work
- scientific article; zbMATH DE number 4213315 (Why is no real title available?)
- scientific article; zbMATH DE number 3938445 (Why is no real title available?)
- scientific article; zbMATH DE number 4078693 (Why is no real title available?)
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 3533576 (Why is no real title available?)
- scientific article; zbMATH DE number 1561761 (Why is no real title available?)
- scientific article; zbMATH DE number 3408799 (Why is no real title available?)
- A Comparison of Deflation and the Balancing Preconditioner
- A Deflated Version of the Conjugate Gradient Algorithm
- A Multigrid Tutorial, Second Edition
- A framework for deflated and augmented Krylov subspace methods
- ARPACK Users' Guide
- Algebraic analysis of two-grid methods: the nonsymmetric case
- Algebraic multigrid based on element interpolation (AMGe)
- Algebraic multigrid theory: The symmetric case
- Analysis of Projection Methods for Solving Linear Systems with Multiple Right-Hand Sides
- Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods
- Computing and deflating eigenvalues while solving multiple right-hand side linear systems with an application to quantum chromodynamics
- Conjugate gradient method with preconditioning by projector
- Deflated and restarted symmetric Lanczos methods for eigenvalues and linear equations with multiple right-hand sides
- Deflation of Conjugate Gradients with Applications to Boundary Value Problems
- Flexible conjugate gradients
- Further comparison of additive and multiplicative coarse grid correction
- Inexact Krylov Subspace Methods for Linear Systems
- Inexact Matrix-Vector Products in Krylov Methods for Solving Linear Systems: A Relaxation Strategy
- Matrix functions
- Methods of conjugate gradients for solving linear systems
- On the Occurrence of Superlinear Convergence of Exact and Inexact Krylov Subspace Methods
- On the construction of deflation-based preconditioners
- On the numerical analysis of oblique projectors
- Parallel iterative methods for sparse linear systems
- Preconditioned conjugate gradients for solving singular systems
- The rate of convergence of conjugate gradients
- Theory of Inexact Krylov Subspace Methods and Applications to Scientific Computing
Cited in
(8)- On the use of deflation to improve the convergence of conjugate gradient iteration
- Accelerating the solution of linear systems appearing in two-phase reservoir simulation by the use of POD-based deflation methods
- A survey of subspace recycling iterative methods
- Two-level Nyström-Schur preconditioner for sparse symmetric positive definite matrices
- A new projected variant of the deflated block conjugate gradient method
- On the spectrum of deflated matrices with applications to the deflated shifted Laplace preconditioner for the Helmholtz equation
- Projections, deflation, and multigrid for nonsymmetric matrices
- A Deflated Version of the Conjugate Gradient Algorithm
This page was built for publication: The deflated conjugate gradient method: convergence, perturbation and accuracy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501271)
