Inexact Gauss Seidel and Coarse Solvers for AMG and s-step CG
Preprint
Abstract
Communication-avoiding Krylov methods require solving small dense Gram systems at each outer iteration. We present a low-synchronization approach based on Forward Gauss--Seidel (FGS), which exploits the structure of Gram matrices arising from Chebyshev polynomial bases. We show that a single FGS sweep is mathematically equivalent to Modified Gram--Schmidt (MGS) orthogonalization in the $A$-norm and provide corresponding backward error bounds. For weak scaling on AMD MI-series GPUs, we demonstrate that 20--30 FGS iterations preserve scalability up to 64 GPUs with problem sizes exceeding 700 million unknowns. We further extend this approach to Algebraic MultiGrid (AMG) coarse-grid solves, removing the need to assemble or factor dense coarse operatorsKeywords
All Related Versions
This publication has 5 references indexed in Scilit:
- On the generation of Krylov subspace basesApplied Numerical Mathematics, 2012
- Inexact Krylov Subspace Methods for Linear SystemsSIAM Journal on Matrix Analysis and Applications, 2004
- Accuracy and Stability of Numerical AlgorithmsJournal of the American Statistical Association, 1999
- On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchyParallel Computing, 1989
- s-step iterative methods for symmetric linear systemsJournal of Computational and Applied Mathematics, 1989