Iterated Gauss–Seidel GMRES
Stephen James Thomas, Erin Carson, Miroslav Rozložńık, Arielle Carr, Katarzyna Świrydowicz · SIAM Journal on Scientific Computing · 2023
Abstract. The GMRES algorithm of Saad and Schultz [ SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856–869] is an iterative method for approximately solving linear systems [Formula: see text], with initial guess [Formula: see text] and residual [Formula: see text]. The algorithm employs the Arnoldi process to generate the Krylov basis vectors (the columns of [Formula: see text]). It is well known that this process can be viewed as a [Formula: see text] factorization of the matrix [Formula: see text] at each iteration. Despite an [Formula: see text] loss of orthogonality, for unit roundoff [Formula: see text] and condition number [Formula: see text], the modified Gram–Schmidt formulation was shown to be backward stable in the seminal paper by Paige et al. [ SIAM J. Matrix Anal. Appl., 28 (2006), pp. 264–284]. We present an iterated Gauss–Seidel formulation of the GMRES algorithm (IGS-GMRES) based on the ideas of Ruhe [ Linear Algebra Appl., 52 (1983), pp. 591–601] and Świrydowicz et al. [ Numer. Linear Algebra Appl., 28 (2020), pp. 1–20]. IGS-GMRES maintains orthogonality to the level [Formula: see text] or [Formula: see text], depending on the choice of one or two iterations; for two Gauss–Seidel iterations, the computed Krylov basis vectors remain orthogonal to working accuracy and the smallest singular value of [Formula: see text] 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 nonnormal systems.