GMRES with Deflated Restarting and Multiple Right-Hand Sides

Ron Morgan

Department of Mathematics, Baylor University, Waco, TX 76798-7328


Abstract

Convergence of restarted GMRES is strongly affected by the presence of small eigenvalues. However, if corresponding eigenvectors are added to the subspace, these eigenvalues are deflated. The method GMRES with Deflated Restarting (GMRES-DR) efficiently adds approximate eigenvectors to a Krylov subspace. This method can generate eigenvectors at the same time that it solves the linear equations. Once the eigenvectors are moderately accurate, the convergence of the linear equations improves. Deflating eigenvalues is particularly useful when there are multiple right-hand sides. The eigenvectors developed while solving the first right-hand side can be used for subsequent ones, and the improvement in convergence can start at the beginning. An occasional projection is sufficient for deflating eigenvalues for the subsequent right-hand sides. We will look at applications to the large matrix problems generated in lattice QCD (quantum chromodynamics). One difficult example has eigenvalues half surrounding the origin in the the complex plane. If 30 approximate eigenvectors are used along with Krylov subspaces of dimension 20, the linear equations with the second right-hand side can be solved three times as fast as with standard GMRES(20). There is additional storage needed for the approximate eigenvectors, but the expense per iteration is about the same. Block methods will also be discussed. A full orthogonalization method such as Block GMRES may have to be restarted frequently if there are limits on the storage or if orthogonalization costs are significant compared to the cost of matrix-vector products. Frequent restarting can strongly impair performance. However, sometimes this problem can be fixed by deflating eigenvalues. The deflation makes the problem easy enough that small Krylov subspaces are effective. Deflation makes block-GMRES more competitive with nonrestarted methods.