GMRES/CR and Arnoldi/Lanczos as Matrix Approximation Problems

Abstract

The GMRES and Arnoldi algorithms, which reduce to the CR and Lanczos algorithms in the symmetric case, both minimize ||p(A)b|| over polynomials p of degree n. The difference is that p is nor- malized at z=0 for GMRES and at z=infinity for Arnoldi. Analogous "ideal GMRES" and "ideal Arnoldi" problems are obtained if one removes b from the discussion and minimizes ||p(A)|| instead. Investigation of these true and ideal approximation problems gives insight into how fast GMRES converges and how the Arnoldi iteration locates eigenvalues.