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).