Generalized Minimal Residual Method - The Method

The Method

Denote the Euclidean norm of any vector v by ||v||. Denote the system of linear equations to be solved by

The matrix A is assumed to be invertible of size m-by-m. Furthermore, it is assumed that b is normalized, i.e., that ||b|| = 1.

The nth Krylov subspace for this problem is

GMRES approximates the exact solution of Ax = b by the vector x_n ∈ K_n that minimizes the Euclidean norm of the residual Ax_n − b.

The vectors b, Ab, …, An−1b might be almost linearly dependent, so instead of this basis, the Arnoldi iteration is used to find orthonormal vectors

which form a basis for K_n. Hence, the vector x_n ∈ K_n can be written as x_n = Q_ny_n with y_n ∈ Rn, where Q_n is the m-by-n matrix formed by q₁, …, q_n.

The Arnoldi process also produces an (n+1)-by-n upper Hessenberg matrix with

Because is orthogonal, we have

where

is the first vector in the standard basis of Rn+1, and

being the first trial vector (usually zero). Hence, can be found by minimizing the Euclidean norm of the residual

This is a linear least squares problem of size n.

This yields the GMRES method. At every step of the iteration:

1. do one step of the Arnoldi method;
2. find the which minimizes ||r_n||;
3. compute ;
4. repeat if the residual is not yet small enough.

At every iteration, a matrix-vector product Aq_n must be computed. This costs about 2m2 floating-point operations for general dense matrices of size m, but the cost can decrease to O(m) for sparse matrices. In addition to the matrix-vector product, O(n m) floating-point operations must be computed at the nth iteration.