A GMRES convergence analysis for localized invariant subspace ill-conditioning

The Generalized Minimal RESidual (gmres) method is a well-established strategy for iteratively solving a large linear system [Formula presented], where [Formula presented] is a nonsymmetric and nonsingular coefficient matrix, and [Formula presented]. In the analysis of its convergence for A diagonalizable, a much used upper bound for the relative residual norm involves a min-max polynomial problem over the set of eigenvalues of A, magnified by the condition number of the eigenvector matrix of A. This latter factor may cause a huge overestimation of the residual norm, making the bound nondescriptive in practice. We show that when a large condition number is caused by the almost linear dependence of a few of the eigenvectors, a more descriptive analysis of the method's behavior can be performed, irrespective of the location of the corresponding eigenvalues. The new analysis aims at capturing how the gmres polynomial deals with the ill-conditioning; as a by-product, a new upper bound for the gmres residual norm is obtained. A variety of numerical experiments illustrate our findings.