Predict-and-Recompute Conjugate Gradient Variants
From MaRDI portal
Publication:5132005
DOI10.1137/19M1276856zbMATH Open1452.65057arXiv1905.01549MaRDI QIDQ5132005FDOQ5132005
Authors: Tyler Chen, Erin Carson 
Publication date: 9 November 2020
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: The standard implementation of the conjugate gradient algorithm suffers from communication bottlenecks on parallel architectures, due primarily to the two global reductions required every iteration. In this paper, we study conjugate gradient variants which decrease the runtime per iteration by overlapping global synchronizations, and in the case of pipelined variants, matrix-vector products. Through the use of a predict-and-recompute scheme, whereby recursively-updated quantities are first used as a predictor for their true values and then recomputed exactly at a later point in the iteration, these variants are observed to have convergence behavior nearly as good as the standard conjugate gradient implementation on a variety of test problems. We provide a rounding error analysis which provides insight into this observation. It is also verified experimentally that the variants studied do indeed reduce the runtime per iteration in practice and that they scale similarly to previously-studied communication-hiding variants. Finally, because these variants achieve good convergence without the use of any additional input parameters, they have the potential to be used in place of the standard conjugate gradient implementation in a range of applications.
Full work available at URL: https://arxiv.org/abs/1905.01549
Recommendations
- scientific article; zbMATH DE number 3956828
- Conjugate gradient type methods and preconditioning
- Steepest Descent and Conjugate Gradient Methods with Variable Preconditioning
- scientific article; zbMATH DE number 3844481
- Constrained and Preconditioned Stochastic Gradient Method
- Preconditioned conjugate gradient algorithms for nonconvex problems
- Conjugate gradient acceleration of iteratively re-weighted least squares methods
- A Multipreconditioned Conjugate Gradient Algorithm
- Conjugate gradient predictor corrector method for solving large scale problems
- Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
Parallel numerical computation (65Y05) Iterative numerical methods for linear systems (65F10) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12)
Cites Work
- BiCGstab(\(l\)) and other hybrid Bi-CG methods
- Title not available (Why is that?)
- Methods of conjugate gradients for solving linear systems
- Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
- The Lanczos and conjugate gradient algorithms in finite precision arithmetic
- Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
- On the real convergence rate of the conjugate gradient method
- s-step iterative methods for symmetric linear systems
- Accuracy of two three-term and three two-term recurrences for Krylov space solvers
- The Lanczos and Conjugate Gradient Algorithms
- Krylov Subspace Methods on Supercomputers
- Practical Use of Polynomial Preconditionings for the Conjugate Gradient Method
- Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem
- Estimating the Attainable Accuracy of Recursively Computed Residual Methods
- Multitasking the conjugate gradient method on the CRAY X-MP/48
- Title not available (Why is that?)
- Communication lower bounds and optimal algorithms for numerical linear algebra
- The Numerical Stability Analysis of Pipelined Conjugate Gradient Methods: Historical Context and Methodology
- Analyzing the Effect of Local Rounding Error Propagation on the Maximal Attainable Accuracy of the Pipelined Conjugate Gradient Method
Cited In (1)
Uses Software
This page was built for publication: Predict-and-Recompute Conjugate Gradient Variants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5132005)
