Introduction to Computational Linear Algebra

Iterative Methods for Systems of Linear Equations 169

6.5.5 Restarted GMRES

GMRES algorithm has long recurrences, in contrary to PCG. Arnoldi’s pro-

cedure requires storing the k + 1 vectors of the basis V

k+1

, thus the memory

requirements increase at each iteration of the GMRES algorithm, whereas

they are fixed in PCG.

Arnoldi’s procedure requires k matrix-vector operations, thus one matrix-

vector per iteration as in PCG. But the orthogonalization involves O(nk

2

)

floating-point operations, thus the complexity is quadratic with the number

k of iterations.

For very large systems arising in real scientific problems, these requirements

are an issue. Thus restarted ...