The GMRES algorithm of Saad and Schultz (1986) is an iterative method for approximately solving linear systems $A{\bf x}={\bf b}$, with initial guess ${\bf x}_0$ and residual ${\bf r}_0 = {\bf b} - A{\bf 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 = [\: {\bf r}_0, AV_k\:]$ 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.
翻译:Saad和Schultz(1986)的GMRES算法是用于近似解线性系统$A{\bf x}={\bf b}$的迭代方法,其中${\bf x}_0$是初始猜测,${\bf r}_0={\bf b}-A{\bf x}_0$是残差。该算法利用Arnoldi过程生成Krylov基向量($V_k$的列)。众所周知,这一过程可以被视为每次迭代矩阵$B_k=[{\bf r}_0,AV_k]$的$QR$分解。尽管存在一个${O}(\epsilon)\kappa(B_k)$的正交性缺失,单位舍入$\epsilon$和条件数$\kappa$,但局部修正Gram-Schmidt公式在Paige等人(2006)的开创性论文中被证明是向后稳定的。我们提出了GMRES算法的迭代Gauss-Seidel公式(IGS-GMRES),基于Ruhe(1983)和Świrydowicz等人(2020)的思想。IGS-GMRES在${O}(\epsilon)\kappa(B_k)$或${O}(\epsilon)$的级别维持正交性,具体取决于选择一次或两次迭代;对于两个Gauss-Seidel迭代,计算的Krylov基向量保持正交到工作精度,而$V_k$的最小奇异值保持接近1。因此,得到的GMRES方法是向后稳定的。我们展示了IGS-GMRES每次迭代仅需要一个同步点即可实现,使其与大规模并行计算环境相关。我们还证明,与MGS-GMRES不同,在IGS-GMRES中,对应于计算近似解的相对Arnoldi残差即使对于高度非正常的系统也不再停滞在机器精度之上。