Extending Elman's Bound for GMRES

If the numerical range of a matrix is contained in the right half-plane, the GMRES algorithm for solving linear systems will make progress at every iteration. In his Ph.D. dissertation, Howard Elman derived a bound that guarantees convergence. When all eigenvalues are in the right half-plane but the numerical range contains the origin, GMRES need not make progress at every step, and Elman's bound does not apply. By solving a Lyapunov equation, one can construct an inner product in which the numerical range is contained in the right half-plane. One can bound GMRES (run in the standard Euclidean norm) by applying Elman's bound in this new inner product, at the cost of a multiplicative constant that characterizes the distortion caused by the change of inner product. Using Lyapunov inverse iteration, one can build a family of suitable inner products, trading off the location of the numerical range with the size of constant. This approach complements techniques recently proposed by Greenbaum and colleagues for eliminating the origin from the numerical range for GMRES convergence analysis.