Near-optimal convergence of the full orthogonalization method

We establish a near-optimality guarantee for the full orthogonalization method (FOM), showing that the overall convergence of FOM is nearly as good as GMRES. In particular, we prove that at every iteration k, there exists an iteration j≤ k for which the FOM residual norm at iteration j is no more than √k+1 times larger than the GMRES residual norm at iteration k. This bound is sharp, and it has implications for algorithms for approximating the action of a matrix function on a vector.