The conjugate gradient (CG) method is a classic Krylov subspace method for solving symmetric positive definite linear systems. We introduce an analogous semi-conjugate gradient (SCG) method for unsymmetric positive definite linear systems. Unlike CG, SCG requires the solution of a lower triangular linear system to produce each semi-conjugate direction. We prove that SCG is theoretically equivalent to the full orthogonalization method (FOM), which is based on the Arnoldi process and converges in a finite number of steps. Because SCG's triangular system increases in size each iteration, we study a sliding window implementation (SWI) to improve efficiency, and show that the directions produced are still locally semi-conjugate. A counterexample illustrates that SWI is different from the direct incomplete orthogonalization method (DIOM), which is FOM with a sliding window. Numerical experiments from the convection-diffusion equation and other applications show that SCG is robust and that the sliding window implementation SWI allows SCG to solve large systems efficiently.
翻译:二次曲线梯度( CG) 方法是一种经典的 Krylov 子空间方法, 用于解决正对正确定线性系统。 我们为非对称正确定线性系统采用了类似的半二次曲线梯度( SCG) 方法。 与 CG 不同, SCG 需要采用下三角线性系统的解决办法, 以产生每个半二次曲线方向。 我们证明, SCG 在理论上相当于完全正对角法( FOM), 这种方法以Arnoldi 进程为基础, 以若干步骤相交。 由于 SCG 的三角系统在每次迭代中都增加了大小, 我们研究滑动窗口执行方法( SWI) 以提高效率, 并显示所制作的方向仍然是本地的半曲线。 一个对应示例显示, SWI 与直接的不完全或高度曲线化方法( DOM) 不同, 即有滑动窗口的FOM 。 从对等- 扩散方和其他应用的数值实验显示, SCG 是稳健的, 并移动窗口执行 SWI 允许 SWI 有效解大型系统 。