A NEWTON BASIS GMRES IMPLEMENTATION

The GMRES method by Saad and Schultz is one of the most popular iterat ive methods for the solution of large sparse non-symmetric linear syst ems of equations. The implementation proposed by Saad and Schultz uses the Arnoldi process and the modified Gram-Schmidt (MGS) method to com pute orthonormal bases of certain Krylov subspaces. The MGS method req uires many vector-vector operations, which can be difficult to impleme nt efficiently on vector and parallel computers due to the low granula rity 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 factorizatio n 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 p erformance.