Spectral factorization of the Krylov matrix and convergence of GMRES

Abstract

Is it possible to use eigenvalues and eigenvectors to establish accurate results on GMRES performance? Existing convergence bounds, that are extensions of analysis of Hermitian solvers like CG and MINRES, provide no useful information when the coefficient matrix is almost defective. In this paper we propose a new framework for using spectral information for convergence analysis. It is based on what we call the spectral factorization of the Krylov matrix. Using the new apparatus, we prove that two related matrices are equivalent in terms of GMRES convergence, and derive necessary conditions for the worst-case right-hand side vector. We also show that for a specific family of application problems, the worst-case vector has a compact form. In addition, we present numerical data that shows that two matrices that yield the same worst-case GMRES behavior may differ significantly in their average behavior. (Also UMIACS-TR-2001-86)