Steepest Descent and Conjugate Gradient Methods with Variable Preconditioning

DOI10.1137/060675290zbMATH Open1156.65030arXivmath/0605767OpenAlexW2161992803WikidataQ56504438 ScholiaQ56504438MaRDI QIDQ3537448FDOQ3537448

Authors: Ilya V. Lashuk, Andrew Knyazev 

Publication date: 6 November 2008

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Abstract: We analyze the conjugate gradient (CG) method with variable preconditioning for solving a linear system with a real symmetric positive definite (SPD) matrix of coefficients $A$. We assume that the preconditioner is SPD on each step, and that the condition number of the preconditioned system matrix is bounded above by a constant independent of the step number. We show that the CG method with variable preconditioning under this assumption may not give improvement, compared to the steepest descent (SD) method. We describe the basic theory of CG methods with variable preconditioning with the emphasis on ``worst case' scenarios, and provide complete proofs of all facts not available in the literature. We give a new elegant geometric proof of the SD convergence rate bound. Our numerical experiments, comparing the preconditioned SD and CG methods, not only support and illustrate our theoretical findings, but also reveal two surprising and potentially practically important effects. First, we analyze variable preconditioning in the form of inner-outer iterations. In previous such tests, the unpreconditioned CG inner iterations are applied to an artificial system with some fixed preconditioner as a matrix of coefficients. We test a different scenario, where the unpreconditioned CG inner iterations solve linear systems with the original system matrix $A$. We demonstrate that the CG-SD inner-outer iterations perform as well as the CG-CG inner-outer iterations in these tests. Second, we show that variable preconditioning may surprisingly accelerate the SD and thus the CG convergence. Specifically, we compare the CG methods using a two-grid preconditioning with fixed and randomly chosen coarse grids, and observe that the fixed preconditioner method is twice as slow as the method with random preconditioning.

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

Recommendations

• scientific article; zbMATH DE number 440634
• New convergence results and preconditioning strategies for the conjugate gradient method
• scientific article; zbMATH DE number 3844481
• scientific article; zbMATH DE number 465452
• Flexible conjugate gradients

zbMATH Keywords

convergencecondition numbersteepest descentinner-outer iterationsGram-Schmidt orthogonalizationHouseholder reflectionconjugate gradient method: variable preconditioning

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35) Orthogonalization in numerical linear algebra (65F25)

Cited In (14)

• A new \textit{walk on equations} Monte Carlo method for solving systems of linear algebraic equations
• Weighted and flexible versions of block CMRH method for solving nonsymmetric linear systems with multiple right-hand sides
• An improved ``walk on equations Monte Carlo algorithm for linear algebraic systems
• Predict-and-Recompute Conjugate Gradient Variants
• Title not available (Why is that?)
• Preconditioned steepest descent-like methods for symmetric indefinite systems
• Equivalent operator preconditioning for elliptic problems
• Steepest descent preconditioning for nonlinear GMRES optimization
• Optimal scaling parameters for sparse grid discretizations.
• A flexible CMRH algorithm for nonsymmetric linear systems
• A link between the steepest descent method and fixed-point iterations
• Adaptive iterative Hessian sketch via \(A\)-optimal subsampling
• Preconditioned steepest descent methods for some nonlinear elliptic equations involving p-Laplacian terms
• A Geometric Convergence Theory for the Preconditioned Steepest Descent Iteration

This page was built for publication: Steepest Descent and Conjugate Gradient Methods with Variable Preconditioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3537448)