Accelerating the Convergence of Restarted GMRES

Allison Baker

Department of Applied Mathematics
University of Colorado at Boulder
Boulder, CO 80309-0526

E. R. Jessup

Department of Computer Science
University of Colorado at Boulder
Boulder, CO 80309-0430


Abstract

Because restarted GMRES is such a popular iterative method for solving nonsymmetric systems of linear equations, its convergence behavior continues to be of interest. We have observed that the residual vectors at the end of each restart cycle often alternate direction in a cyclic fashion. This alternating phenomenon is particularly noticeable in matrices that are nearly normal, and it slows convergence. We present a new algorithm that breaks this alternating pattern and thereby accelerates convergence. In theory, this new algorithm resembles a full conjugate gradient method with polynomial preconditioning, and its implementation requires minimal changes to the standard restarted GMRES algorithm. We compare our algorithm with hybrid iterative algorithms, discuss the theory, and present numerical results.