Volume 60, pp. 421-427, 2024.

Near-optimal convergence of the full orthogonalization method

Tyler Chen and Gérard Meurant

Abstract

We establish a near-optimality guarantee for the full orthogonalization method (FOM), showing that the \emph{overall} convergence of FOM is nearly as good as GMRES. In particular, we prove that at every iteration $k$, there exists an iteration $j\leq k$ for which the FOM residual norm at iteration $j$ is no more than $\sqrt{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.

Full Text (PDF) [471 KB], BibTeX

Key words

Full Orthogonalization Method, GMRES

AMS subject classifications

65F10

< Back