# Operation count for GMRES

One can use GMRES as it is, but there is also a version of GMRES called k-step restarted GMRES, which is used for large matrices, where $$k$$ is some fixed number of steps after which we take a new $$x_0$$ and restart the algorithm to save memory storage.

I want to count the number of flops and memory storage required in either case. Concerning the flops, as far as I understand, we have the following:

• $$O(n)$$ steps in the main loop, $$O(n)$$ steps for Arnoldi iteration, and $$O(n)$$ steps for matrix multiplication in the least squares solution. So the total comes to $$O(n^3)$$. Is this true?

For the restarted algorithm, we have:

• $$O(k^3)$$ steps until convergence for each restart. Is this true?

Now, I don't really know how to calculate memory storage. Could someone please help me with this part?

Performing $$k$$ steps of GMRES uses $$O(n k^2)$$ time and $$O(n k)$$ memory. In other words, the algorithm gets more and more expensive with each additional iteration. In theory, the algorithm terminates in $$k \le n$$ steps (ignoring round-off), thereby yielding a worst-case cubic $$O(n^3)$$ time and quadratic $$O(n^2)$$ memory figure.
In practice, we manually terminate the algorithm after $$k=O(1)$$ steps to yield a linear $$O(n)$$ time and memory figure. We do this with the hope that convergence is sufficiently rapid that the $$k$$-th iterate will already satisfy error tolerances. In some special cases, we will be able to prove this.
Nevertheless, when $$k$$ is large, the cost of the $$k$$-th iteration may still be too large. We can reduce this by restarting GMRES after every $$p \le k$$ steps. In this case, the algorithm has a fixed $$O(n p^2) = O(n)$$ time and $$O(n p) = O(n)$$ memory complexity, independent of the final iterate count $$k$$. The reduction in complexity comes at a price though: restarted GMRES (provably) converges slower than GMRES, and may also stagnate.
• Sorry, it's $O(nk^2)$ time after $k$ iterations. The $k$-th iteration computes the inner product of a length-$n$ vector against $k$ bases. This uses $O(kn)$ time and memory. Sum the total work done over iterations $1,2,3,\ldots,k$ gets you the squared factor. – Richard Zhang Dec 11 '18 at 18:40
• Rather than get lost in the nitty-gritty of the Arnoldi, it's helpful to take a step back and ask, "what pieces of information do we need?" In the case of GMRES, we fundamentally need to carry $k$ length-$n$ vectors. There's some short-cuts we can take to avoid redundant arithmetic operators, but we will never get around needing to store and multiply the $k$ length-$n$ vectors at each iteration. – Richard Zhang Dec 11 '18 at 18:43