Operation count for GMRES

Question

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?

Answer 1

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.