The deflated conjugate gradient method: convergence, perturbation and accuracy

DOI10.1016/J.LAA.2016.10.027zbMATH Open1352.65098arXiv1209.1963OpenAlexW2963286833MaRDI QIDQ501271FDOQ501271

Sumit K. Garg, Yong-Cai Geng

Publication date: 29 December 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1209.1963

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

zbMATH Keywords

convergencemultigridperturbationconjugate gradientsdeflation

Mathematics Subject Classification ID

Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10)

Cites Work

• ARPACK Users' Guide
• Title not available (Why is that?)
• Title not available (Why is that?)
• Methods of conjugate gradients for solving linear systems
• Parallel iterative methods for sparse linear systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The rate of convergence of conjugate gradients
• Preconditioned conjugate gradients for solving singular systems
• Further comparison of additive and multiplicative coarse grid correction
• On the construction of deflation-based preconditioners
• Deflation of Conjugate Gradients with Applications to Boundary Value Problems
• Title not available (Why is that?)
• A Multigrid Tutorial, Second Edition
• Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods
• Conjugate gradient method with preconditioning by projector
• Theory of Inexact Krylov Subspace Methods and Applications to Scientific Computing
• A Deflated Version of the Conjugate Gradient Algorithm
• A Comparison of Deflation and the Balancing Preconditioner
• Title not available (Why is that?)
• Algebraic multigrid theory: The symmetric case
• A framework for deflated and augmented Krylov subspace methods
• On the Occurrence of Superlinear Convergence of Exact and Inexact Krylov Subspace Methods
• On the Numerical Analysis of Oblique Projectors
• Matrix functions
• Algebraic multigrid based on element interpolation (AMGe)
• Algebraic analysis of two-grid methods: The nonsymmetric case
• Inexact Krylov Subspace Methods for Linear Systems
• Computing and Deflating Eigenvalues While Solving Multiple Right-Hand Side Linear Systems with an Application to Quantum Chromodynamics
• Inexact Matrix-Vector Products in Krylov Methods for Solving Linear Systems: A Relaxation Strategy
• Flexible conjugate gradients
• Deflated and Restarted Symmetric Lanczos Methods for Eigenvalues and Linear Equations with Multiple Right-Hand Sides
• Analysis of Projection Methods for Solving Linear Systems with Multiple Right-Hand Sides

Cited In (8)

• Two-Level Nyström--Schur Preconditioner for Sparse Symmetric Positive Definite Matrices
• A new projected variant of the deflated block conjugate gradient method
• Projections, Deflation, and Multigrid for Nonsymmetric Matrices
• A Deflated Version of the Conjugate Gradient Algorithm
• On the use of deflation to improve the convergence of conjugate gradient iteration
• A survey of subspace recycling iterative methods
• Accelerating the solution of linear systems appearing in two-phase reservoir simulation by the use of POD-based deflation methods
• On the Spectrum of Deflated Matrices with Applications to the Deflated Shifted Laplace Preconditioner for the Helmholtz Equation

Uses Software

• ARPACK

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)