Unrestarted GMRES has a sparse matvec plus orthogonalization work bound

The canonical convention [F1] identifies the stored count with $s=\mathrm{nnz}(A)$. Each of at most $m$ columns uses one sparse matvec, which costs $O(s)$ by [F2] and [F3]. Summing over the columns gives $O(ms)$ work; if breakdown stops the run at $d<m$, the sum through $d$ is no larger.

At column $j$, one complete MGS pass computes $j$ length-$n$ inner products and $j$ length-$n$ vector updates, hence $O(jn)$ arithmetic; two passes multiply this by the fixed factor two. Therefore total orthogonalization work through $m$ columns is $O(n{\sum }_{j=1}^{m}j)=O(m^{2}n)$, and stopping earlier only reduces it.

In the no-breakdown branch, [F5] gives a projected matrix ${\bar{H}}_m\in {\mathbb{R}}^{(m+1)\times m}$ with nonzero subdiagonal entries $h_{j+1,j}$. For orthonormal $Q_{m+1}$ and $r_0=\beta q_1$, each candidate $x_0+Q_{m}y$ has residual $b-A(x_0+Q_{m}y)=Q_{m+1}(\beta e_1-{\bar{H}}_{m}y)\mathrm{.}$ Therefore [F6] reduces GMRES minimization to this projected least-squares problem. The submatrix formed by rows $2,\dots ,m+1$ is upper triangular with diagonal $h_{2,1},\dots ,h_{m+1,m}$, so its columns are linearly independent. Thus ${\bar{H}}_m$ has full column rank. Applying one plane Givens rotation to each row pair eliminates one subdiagonal entry while preserving the Euclidean least-squares norm; the rotations create an upper-triangular $m\times m$ factor with nonzero diagonal. At column $j$, applying the previous at most $j-1$ rotations and forming the new rotation takes $O(j)$ scalar operations; all columns cost $O(m^2)$. Back substitution in the nonsingular triangular factor takes $O(m^2)$ operations, and forming the Krylov correction costs $O(mn)$. By [F6] this solves the specified GMRES projected least-squares problem.

Since $n\ge 1$ and $m\le n$, $m^2\le m^{2}n$ and $mn\le m^{2}n$. Adding the work bounds in steps 1.1, 1.2, and 1.3 gives $O(ms+m^{2}n)$. Storing at most $m+1$ length-$n$ basis vectors takes $O(mn)$ slots; the Hessenberg and Givens data take $O(m^2)$ slots; temporary vectors use $O(n)$ slots. Since $m\le n$, both $m^2$ and $n$ are at most $mn$, proving the storage bound. If breakdown occurs at column $d<m$, the already formed basis and projected data use at most the same bounds with $d$ in place of $m$, and no fallback least-squares solve is included.