1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Richard Zhang
    Dec 11, 2018 at 18:40
  • $\begingroup$ 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. $\endgroup$
    – Richard Zhang
    Dec 11, 2018 at 18:43
  • $\begingroup$ The fact that CG is able to avoid carrying the basis explicitly comes down to a three-term recursion. Unfortunately, such a recursion is guaranteed not to exist for nonsymmetric matrices due to a famous theorem by Faber and Manteuffel. $\endgroup$
    – Richard Zhang
    Dec 11, 2018 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.