What are the major differences between GMRES and FOM?

Question

I am reading Professor Saad's "Iterative Methods for Sparse Linear Systems" (2nd edition).

The basic algorithm for FOM is given on page 166 and the basic algorithm for GMRES is given on page 172.

Both FOM and GMRES appear to build the same Krylov subspace and upper Hessenberg matrix.

However, at the very end of the algorithms, FOM solves a linear system to obtain $x_m$ (seemingly discarding the last row of the Hessenberg matrix) while GMRES solves a least squares problem with the whole Hessenberg matrix to obtain $x_m$. Then, the solution to both problems is $y_m = V_m x_m + x_0$ and I think the $V_m$ are the same in both algorithms.

My questions are:

1. Why does this (in my opinion, seemingly small) difference create two separate algorithms?

2. Why is GMRES used widely over FOM?

Clearly I seem to be missing something, but I don't know what.

Answer 1

There is one major difference between GMRES over FOM. It is also the reason why I would recommend GMRES over FOM.

By design, GMRES minimizes the residual over the Krylov subspace that also contains the current FOM approximation. If the goal is to minimize the residual, then GMRES is superior to FOM as the main effort is the construction of Krylov subspace shared by the two methods. However, this particular feature of GMRES offers another advantage.

In exact arithmetic, the residuals obtained by GMRES form a decreasing sequence. You are certain that the GMRES residuals will not increase in the absence of rounding errors. Once the computed residual deviates from this simple pattern there is nothing to be gained from further iterations.

In the case of FOM an arbitrary positive residual curve is possible. You can still detect when further iterations are pointless, but you must measure the size of the subdiagonal elements $h_{j+1,j}$ as $V_j$ is an invariant subspace for a matrix $A + \Delta A$ where $\|\Delta A\|_2 = h_{j+1,j}$. You will find an explicit formula for $\Delta A$ in Saad's book. In other words, once $h_{j+1,j}$ drops below $\tau \|A\|_2$ where $\tau$ is the normwise relative error associated with computing $A$, there is no point in doing further Arnoldi steps. At this stage it is entirely possible that we have solved the true problem exactly.

Deciding when further FOM iterations are pointless requires more knowledge and insight than deciding when further GMRES iterations are pointless.