The Generalized Minimum Residual (GMRES) method is designed to solve nonsymmetric linear systems (see Saad and Schultz [189]). The most popular form of GMRES is based on the modified Gram-Schmidt procedure, and uses restarts to control storage requirements.
If no restarts are used, GMRES
(like any orthogonalizing Krylov-subspace method) will
converge in no more than steps (assuming exact arithmetic). Of
course this is of no practical value when
is large; moreover, the
storage and computational requirements in the absence of restarts are
prohibitive. Indeed, the crucial element for successful application
of GMRES(
) revolves around the decision of when to restart; that
is, the choice of
. Unfortunately, there exist examples for which
the method stagnates and convergence takes place only
at the
th step. For such systems, any choice of
less than
fails to converge.
Saad and Schultz [189] have proven several useful results.
In particular, they show that if the coefficient matrix is real
and nearly positive definite, then a ``reasonable'' value for
may be selected. Implications of the choice of
are discussed
below.