CGMN Revisited: Robust and Efficient Solution of Stiff Linear Systems Derived from Elliptic Partial Differential Equations
CGMN Revisited: Robust and Efficient Solution of Stiff Linear Systems Derived from Elliptic Partial Differential Equations
复制标题
DOI：
10.1145/1391989.1391991
复制
发表时间：
2008-10-01
影响因子：
2.7
通讯作者：
Gordon, Rachel
中科院分区：
文献类型：
--
作者：
Gordon, Dan;Gordon, Rachel
给定一个线性系统Ax = b，可以构造一个相关的“正规方程”系统AA(T)y = b, x = a (T)y。Bjorck和Elfving已经证明，应用于正态方程的SSOR算法可以通过共轭梯度算法（CG）来加速。由此产生的算法，称为CGMN，是减少误差的，并且在理论上，即使在方程系统不一致和/或非平方时，它也总是收敛的。常规方程上的SSOR相当于Kaczmarz算法（KACZ），具有固定的松弛参数，对原始方程进行双重（向前和向后）扫描。对椭圆型对流扩散偏微分方程（PDEs）的中心差分离散得到的9个著名的大型稀疏线性系统进行了CGMN测试。其中8个偏微分方程是强对流主导的，众所周知，这些偏微分方程产生了具有大非对角元素的非常坚硬的系统。将CGMN与一些最先进的Krylov子空间方法进行了比较：重新启动的GMRES、Bi-CGSTAB和CGS。在加和不加各种预处理剂的情况下对这些方法进行了测试。CGMN在所有情况下都是收敛的，而前面的算法/预条件组合都没有达到这种水平的鲁棒性。此外，在不同的网格大小上，随着网格的细化，迭代次数只会逐渐增加。在对流占优的8种情况下，CGMN的初始收敛速度优于其他所有算法和预处理的组合，残差单调减小。对CGNR算法也进行了测试，其鲁棒性与CGMN相当，但速度较慢。
Given a linear system Ax = b, one can construct a related "normal equations" system AA(T)y = b, x = A(T)y. Bjorck and Elfving have shown that the SSOR algorithm, applied to the normal equations, can be accelerated by the conjugate gradient algorithm (CG). The resulting algorithm, called CGMN, is error-reducing and in theory it always converges even when the equation system is inconsistent and/or nonsquare. SSOR on the normal equations is equivalent to the Kaczmarz algorithm (KACZ), with a fixed relaxation parameter, run in a double (forward and backward) sweep on the original equations. CGMN was tested on nine well-known large and sparse linear systems obtained by central-difference discretization of elliptic convection-diffusion partial differential equations (PDEs). Eight of the PDEs were strongly convection-dominated, and these are known to produce very stiff systems with large off-diagonal elements. CGMN was compared with some of the foremost state-of-the art Krylov subspace methods: restarted GMRES, Bi-CGSTAB, and CGS. These methods were tested both with and without various preconditioners. CGMN converged in all the cases, while none of the preceding algorithm/preconditioner combinations achieved this level of robustness. Furthermore, on varying grid sizes, there was only a gradual increase in the number of iterations as the grid was refined. On the eight convection-dominated cases, the initial convergence rate of CGMN was better than all the other combinations of algorithms and preconditioners, and the residual decreased monotonically. The CGNR algorithm was also tested, and it was as robust as CGMN, but slower.