Implicity Restarted GMRES and Arnoldi Methods for Nonsymmetric Systems of Equations

Morgan 9522612在这个项目中，我们将研究求解大型非对称线性方程组的重启GMRES方法的改进。我们的目标是开发一种与QMR等短递归Lanczos方法竞争的方法，但仍保持GMRES的理想性质。这些性质包括从子空间中提取最小剩余解、一般稳定的收敛和数值稳定性。还希望不显著增加每次迭代的成本和存储需求。通过在子空间中加入近似特征向量，可以提高GMRES的收敛速度。一旦这些特征值基本上从矩阵的频谱中减去，即使从频谱中删除几个小的特征值也可以显著提高收敛速度。在这个项目中，我们提出了一种新的、有效的包含特征向量的方法。Sorensen的隐式QR Arnoldi特征值方法与Arnoldi的内特征值方法相结合。令人惊讶的结果是，近似特征向量成为新的Krylov子空间的一部分。这个Krylov子空间可以与GMRES一起使用。在矩阵向量乘积昂贵的情况下，每次迭代的代价甚至比常规GMRES更小，而且所需的迭代次数有时会大大减少。所得到的隐式重启GMRES方法将被研究并与其他方法进行比较。***

Morgan 9522612 In this project, improvements of the restarted GMRES method for solving large nonsymmetric systems of linear equations will be investigated. The goal is to develop a method that is competitive with short recurrence Lanczos methods such as QMR, but maintains the desirable properties of GMRES. These properties include extraction of the minimum residual solution from the subspace, generally steady convergence, and numerical stability. It is also desired to not significantly raise cost per iteration and storage requirements. The convergence of GMRES can be improved by including approximate eigenvectors in the subspace. Once these eigenvalues are essentially deflated from the spectrum of the matrix, removing even just a few small eigenvalues from the spectrum can significantly improve the convergence. In this project a new and efficient way of including eigenvectors is proposed. Sorensen's implicit-QR Arnoldi method for eigenvalues is combined with an interior eigenvalue version of Arnoldi. The surprising result is that the approximate eigenvectors become part of a new Krylov subspace. This Krylov subspace can be used with GMRES. The expense per iteration is even less than that of regular GMRES for the case where matrix-vector products are expensive, and the number of iterations needed is sometimes greatly reduced. The resulting implicitly restarted GMRES method will be studied and compared with other methods. ***