Near-optimal convergence of the full orthogonalization method

This is a companion piece to Chen & Meurant (2024).

Code to replicate the figures in the corresponding paper can be found on Github.

Introduction¶

The full orthogonalization method (FOM) Saad (1981) and the generalized minimal residual method (GMRES) Saad & Schultz (1986) are two Krylov subspace methods used for solving a real or complex non-symmetric linear system of equations. Note that if $\vec{A}$ is symmetric GMRES is mathematically equivalent to MINRES Paige & Saunders (1975), and if $\vec{A}$ is symmetric positive definite FOM is mathematically equivalent to conjugate gradient Hestenes & Stiefel (1952). While this is relevant for efficient implementation, it does not impact the exact arithmetic theory in this note.

Assuming an initial guess $\vec{x}_0 = \vec{0}$, both FOM and GMRES produce iterates from the Krylov subspace

but according to slightly different formulas.

It is well-known that the GMRES iterates satisfy a residual optimality guarantee:

Hence, the GMRES residual norms are non-increasing and are optimal among Krylov subspace methods. This optimality guarantee leads to well-known results on the rate of convergence of the residual norms in terms of quantities such as the condition number of $\vec{A}$ Saad (2003). On the other hand, the FOM residual norms often appear oscillatory, with large jumps. In fact, it is easy to construct examples for which $\|\vec{r}_k^{\mathrm{F}}\|_2/\|\vec{r}_0^{\mathrm{F}}\|_2$ can be arbitrarily large Meurant & Duintjer Tebbens (2020)!

The main result of our paper is to prove that, in an overall sense, FOM behaves nearly as well as GMRES:

The paper is actually very short and easy to read, so I’m not including that much more here.