A Newton Basis Gmres Implementation
A Newton Basis Gmres Implementation
复制标题
牛顿基 Gmres 实现
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
D. Hut
中科院分区：
文献类型：
--
作者：
D. Hut
Saad 和 Schultz 提出的 GMRES 方法是求解大型稀疏非对称线性方程组最流行的迭代方法之一。 Saad 和 Schultz 提出的实现使用 Arnoldi 过程和改进的 Gram-Schmidt (MGS) 方法来计算某些 Krylov 子空间的正交基。 MGS 方法需要许多向量-向量运算，由于这些运算的粒度较低，因此很难在向量和并行计算机上有效实现。我们提出了 GMRES 方法的新实现，其中对于使用的每个 Krylov 子空间，我们首先确定牛顿基，然后通过计算矩阵的 QR 分解来将其正交化，该矩阵的列是牛顿基的向量。通过这种方式，我们通过计算稠密矩阵的 QR 分解任务来代替 MGS 方法的向量-向量运算。这使得实现更加灵活，并提供了使计算适应手头计算机以获得更好性能的可能性。
The GMRES method by Saad and Schultz is one of the most popular iterative methods for the solution of large sparse non-symmetric linear systems of equations. The implementation proposed by Saad and Schultz uses the Arnoldi process and the modified Gram-Schmidt (MGS) method to compute orthonormal bases of certain Krylov subspaces. The MGS method requires many vector-vector operations, which can be difficult to implement efficiently on vector and parallel computers due to the low granularity of these operations. We present a new implementation of the GMRES method in which, for each Krylov subspace used, we first determine a Newton basis, and then orthogonalize it by computing a QR factorization of the matrix whose columns are the vectors of the Newton basis. In this way we replace the vector-vector operations of the MGS method by the task of computing a QR factorization of a dense matrix. This makes the implementation more flexible, and provides a possibility to adapt the computations to the computer at hand in order to achieve better performance.