Iterated Gauss–Seidel GMRES

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 \(A\mathbf{x}=\mathbf{b}\), with initial guess \(\mathbf{x}_0\) and residual \(\mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0\). 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 \(B_k = [\: \mathbf{r}_0, AV_k\:]\) at each iteration. Despite an \({\cal O}(\varepsilon )\kappa (B_k)\) loss of orthogonality, for unit roundoff \(\varepsilon\) and condition number \(\kappa\), 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 \({\cal O}(\varepsilon )\kappa (B_k)\) or \({\cal O}(\varepsilon )\), 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 \(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 nonnormal systems.KeywordsGram–SchmidtKrylovArnoldi-QRGMRESorthogonal complementGauss–SeidelMSC codes65F1065F5065F2568W1065Y05

Topics & Concepts