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?