# What are the major differences between GMRES and FOM?

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.

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.