The generalized minimal residual (GMRES) method (Saad and Schultz 1986) is an extension of the minimal residual method (MINRES), which is only applicable to symmetric systems, to unsymmetric systems. Like MINRES, it generates a sequence of orthogonal vectors, but in the absence of symmetry this can no longer be done with short recurrences; instead, all previously computed vectors in the orthogonal sequence have to be retained. For this reason, "restarted" versions of the method are used.
In the conjugate gradient method, the residuals form an orthogonal basis for the space
 |
In GMRES, this basis is formed explicitly:
The reader may recognize this as a modified Gram-Schmidt orthonormalization. Applied to the Krylov sequence 
this orthogonalization is called the "Arnoldi
method" (Arnoldi 1951). The inner product coefficients 
and 
are stored in an upper Hessenberg
matrix.
The GMRES iterates are constructed as
 |
where the coefficients 
have been chosen to minimize the residual norm 
. The GMRES algorithm has the property that this
residual norm can be computed without the iterate having been formed. Thus, the expensive
action of forming the iterate can be postponed until the residual norm is deemed
small enough.
In this scheme, UPDATE
replaces the following computations:
The generalized minimal residual method is designed to solve nonsymmetric linear systems (Saad and Schultz 1986) The most popular form of GMRES is based on a modified Gram-Schmidt orthonormalization 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 (1986) 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.
A common implementation of GMRES is suggested by Saad and Schultz (1986) and relies on using modified Gram-Schmidt orthonormalization. Householder transformations, which are relatively costly but stable, have also been proposed. The Householder approach results in a three-fold increase in work associated with inner products and vector updates (not with matrix vector products); however, convergence may be better, especially for ill-conditioned systems (Walker 1988). From the point of view of parallelism, Gram-Schmidt orthonormalization may be preferred, giving up some stability for better parallelization properties (Demmel et al. 1993). Here we adopt the modified Gram-Schmidt approach.
The major drawback to GMRES is that the amount of work and storage required per iteration rises linearly with the iteration count. Unless one is fortunate enough to obtain
extremely fast convergence, the cost will rapidly become prohibitive. The usual way
to overcome this limitation is by restarting the iteration. After a chosen number
of iterations 
, the accumulated data are cleared and the intermediate results
are used as the initial data for the next 
iterations. This procedure is repeated until convergence is
achieved. The difficulty is in choosing an appropriate value for 
. If 
is too small, GMRES(
) may be slow to converge, or fail to converge entirely. A
value of 
that is larger than necessary involves excessive work (and
uses more storage). Unfortunately, there are no definite rules governing the choice
of 
;
choosing when to restart is a matter of experience.
For a discussion of GMRES for vector and shared memory computers see Dongarra et al. (1991). For more general architectures, see Demmel et al. (1993).
