论文标题
迭代的高斯 - 塞德尔GMRE
Iterated Gauss-Seidel GMRES
论文作者
论文摘要
Saad and Schultz（1986）的GMRE算法是一种迭代方法，用于求解线性系统$ a {\ bf x} = {\ bf b} $，初始猜测$ {\ bf x} _0 $和残留$ {\ bf r} $ {\ bf r} _0 $}该算法采用Arnoldi过程来生成Krylov基矢量（$ v_k $的列）。众所周知，此过程可以看作是矩阵$ b_k = [\：{\ bf r} _0，av_k \：] $的$ qR $分解。尽管$ {o}（ε）κ（b_k）$正交性损失，对于单位圆形$ε$和条件编号$κ$，但Paige等人的经过修改的革兰氏schmidt配方在精确的纸上显示出稳定的稳定。 （2006）。我们根据Ruhe（1983）和Świrydowicz等人的思想提出了GMRES算法（IGS-GMRE）的迭代高斯式表述。 （2020）。 IGS-GMRE将正交性保持到级别$ {o}（ε）κ（b_k）$或$ {o}（ε）$，具体取决于一两个迭代的选择；对于两个高斯式迭代，计算出的Krylov基矢量仍然与工作精度正交，并且$ v_k $的最小单数值仍然接近一个。因此，产生的GMRE方法是向后稳定的。我们表明，IGS-GMRE只能通过迭代单个同步点来实现，这使其与大规模并行计算环境相关。我们还证明，与MGS-gmres不同，在IgS-gmres中，相对的Arnoldi残差对应于计算的近似解决方案，即使对于高度非正常系统，也不再停滞在机器上的精度。
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}(ε)κ(B_k)$ loss of orthogonality, for unit roundoff $ε$ and condition number $κ$, 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 Świrydowicz et al. (2020). IGS-GMRES maintains orthogonality to the level ${O}(ε)κ(B_k)$ or ${O}(ε)$, 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.
