Generalized Minimal Residual Method

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 {A^kr^((0))} this orthogonalization is called the "Arnoldi method" (Arnoldi 1951). The inner product coefficients (w^((i)),v^((k))) and |w^((i))| are stored in an upper Hessenberg matrix.

The GMRES iterates are constructed as


where the coefficients y_k have been chosen to minimize the residual norm |b-Ax^((i))|. 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(x^~,i) 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 n steps (assuming exact arithmetic). Of course this is of no practical value when n is large; moreover, the storage and computational requirements in the absence of restarts are prohibitive. Indeed, the crucial element for successful application of GMRES(m) revolves around the decision of when to restart; that is, the choice of m. Unfortunately, there exist examples for which the method stagnates and convergence takes place only at the nth step. For such systems, any choice of m less than n fails to converge.

Saad and Schultz (1986) have proven several useful results. In particular, they show that if the coefficient matrix A is real and nearly positive definite, then a "reasonable" value for m may be selected. Implications of the choice of m 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 m, the accumulated data are cleared and the intermediate results are used as the initial data for the next m iterations. This procedure is repeated until convergence is achieved. The difficulty is in choosing an appropriate value for m. If m is too small, GMRES(m) may be slow to converge, or fail to converge entirely. A value of m that is larger than necessary involves excessive work (and uses more storage). Unfortunately, there are no definite rules governing the choice of m; 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).

See also

Biconjugate Gradient Method, Chebyshev Iteration, Conjugate Gradient Method on the Normal Equations Conjugate Gradient Method, Conjugate Gradient Squared Method, Flexible Generalized Minimal Residual Method, Linear System of Equations, Minimal Residual Method, Nonstationary Iterative Method, Preconditioner, Quasi-Minimal Residual Method Stationary Iterative Method, Symmetric LQ Method, Transpose-Free Quasi-Minimal Residual Method

This entry contributed by Noel Black and Shirley Moore, adapted from Barrett et al. (1994) (author's link)

Explore with Wolfram|Alpha


Arnoldi, W. "The Principle of Minimized Iterations in the Solution of the Matrix Eigenvalue Problem." Quart. Appl. Math. 9, 17-29, 1951.Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; and van der Vorst, H. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed. Philadelphia, PA: SIAM, 1994., J.; Heath, M.; and van der Vorst, H. "Parallel Numerical Linear Algebra." In Acta Numerica, Vol. 2. Cambridge, England: Cambridge University Press, 1993.Dongarra, J.; Duff, I.; Sorensen, D.; and van der Vorst, H. Solving Linear Systems on Vector and Shared Memory Computers. Philadelphia, PA: SIAM, 1991.Saad, Y. and Schultz, M. "GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems." SIAM J. Sci. Statist. Comput. 7, 856-869, 1986.Walker, H. F. "Implementation of the GMRES Method using Householder Transformations." SIAM J. Sci. Statist. Comput. 9, 152-163, 1988.

Referenced on Wolfram|Alpha

Generalized Minimal Residual Method

Cite this as:

Black, Noel and Moore, Shirley. "Generalized Minimal Residual Method." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications