Predict-and-Recompute Conjugate Gradient Variants
From MaRDI portal
Publication:5132005
DOI10.1137/19M1276856zbMATH Open1452.65057MaRDI QIDQ5132005FDOQ5132005
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.
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
Cites work
- scientific article; zbMATH DE number 3915502 (Why is no real title available?)
- scientific article; zbMATH DE number 1049350 (Why is no real title available?)
- Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem
- Accuracy of two three-term and three two-term recurrences for Krylov space solvers
- Analyzing the effect of local rounding error propagation on the maximal attainable accuracy of the pipelined conjugate gradient method
- Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
- BiCGstab(\(l\)) and other hybrid Bi-CG methods
- Communication lower bounds and optimal algorithms for numerical linear algebra
- Estimating the Attainable Accuracy of Recursively Computed Residual Methods
- Krylov Subspace Methods on Supercomputers
- Methods of conjugate gradients for solving linear systems
- Multitasking the conjugate gradient method on the CRAY X-MP/48
- On the real convergence rate of the conjugate gradient method
- Practical Use of Polynomial Preconditionings for the Conjugate Gradient Method
- Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
- The Lanczos and Conjugate Gradient Algorithms
- The Lanczos and conjugate gradient algorithms in finite precision arithmetic
- The numerical stability analysis of pipelined conjugate gradient methods: historical context and methodology
- s-step iterative methods for symmetric linear systems
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)
