Stagnation of GMRES

Abstract

We study problems for which the iterative method \gmr for solving linear systems of equations makes no progress in its initial iterations. Our tool for analysis is a nonlinear system of equations, the stagnation system, that characterizes this behavior. For problems of dimension 2 we can solve this system explicitly, determining that every choice of eigenvalues leads to a stagnating problem for eigenvector matrices that are sufficiently poorly conditioned. We partially extend this result to higher dimensions for a class of eigenvector matrices called extreme. We give necessary and sufficient conditions for stagnation of systems involving unitary matrices, and show that if a normal matrix stagnates then so does an entire family of nonnormal matrices with the same eigenvalues. Finally, we show that there are real matrices for which stagnation occurs for certain complex right-hand sides but not for real ones. (Also UMIACS-TR-2001-74)