Iterated Gauss-Seidel GMRES

DOI10.1137/22M1491241MaRDI QIDQ6399289zbMATH OpenOpenAlexFDO

Authors Stephen J. Thomas, Erin Carson, Miroslav Rozložník, Arielle Carr, Katarzyna Świrydowicz

Publication date 16 May 2022

Full work available at URL https://doi.org/10.1137/22m1491241

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Orthogonalization in numerical linear algebra (65F25) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Parallel algorithms in computer science (68W10)

Abstract: The GMRES algorithm of Saad and Schultz (1986) is an iterative method for approximately solving linear systems $$, with initial guess $$ and residual $$. The algorithm employs the Arnoldi process to generate the Krylov basis vectors (the columns of $V_k$). It is well known that this process can be viewed as a $QR$ factorization of the matrix $$ at each iteration. Despite an $O(epsilon)kappa(B_k)$ loss of orthogonality, for unit roundoff $epsilon$ and condition number $kappa$, the modified Gram-Schmidt formulation was shown to be backward stable in the seminal paper by Paige et al. (2006). We present an iterated Gauss-Seidel formulation of the GMRES algorithm (IGS-GMRES) based on the ideas of Ruhe (1983) and '{S}wirydowicz et al. (2020). IGS-GMRES maintains orthogonality to the level $O(epsilon)kappa(B_k)$ or $O(epsilon)$, depending on the choice of one or two iterations; for two Gauss-Seidel iterations, the computed Krylov basis vectors remain orthogonal to working precision and the smallest singular value of $V_k$ remains close to one. The resulting GMRES method is thus backward stable. We show that IGS-GMRES can be implemented with only a single synchronization point per iteration, making it relevant to large-scale parallel computing environments. We also demonstrate that, unlike MGS-GMRES, in IGS-GMRES the relative Arnoldi residual corresponding to the computed approximate solution no longer stagnates above machine precision even for highly non-normal systems.

Recommendations

• scientific article; zbMATH DE number 592765
• Numerical stability of GMRES
• scientific article; zbMATH DE number 434530
• Modified Gram-Schmidt (MGS), Least Squares, and Backward Stability of MGS-GMRES
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems

Cited in

(5)

• Efficient GMRES+AMG on GPUs: composite smoothers and mixed V-cycles
• Low-synchronization Arnoldi algorithms with application to exponential integrators
• Augmented MGS-CGS block-Arnoldi recycling solvers
• Reorthogonalized Pythagorean variants of block classical Gram-Schmidt
• Gram decay, intrinsic information dimension, and backward stability of s-step GMRES

This page was built for publication: Iterated Gauss-Seidel GMRES

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