In mathematics, the generalized minimal residual method (GMRES) is an iterative method for the numerical solution of an indefinite nonsymmetric system of linear equations.
The method approximates the solution by the vector in a Krylov subspace with minimal residual.
The GMRES method was developed by Yousef Saad and Martin H. Schultz in 1986.
[1] It is a generalization and improvement of the MINRES method due to Paige and Saunders in 1975.
GMRES is a special case of the DIIS method developed by Peter Pulay in 1980.
Denote the (square) system of linear equations to be solved by
The matrix A is assumed to be invertible of size m-by-m.
might be close to linearly dependent, so instead of this basis, the Arnoldi iteration is used to find orthonormal vectors
This is a linear least squares problem of size n. This yields the GMRES method.
floating-point operations for general dense matrices of size
The nth iterate minimizes the residual in the Krylov subspace
After m iterations, where m is the size of the matrix A, the Krylov space Km is the whole of Rm and hence the GMRES method arrives at the exact solution.
However, the idea is that after a small number of iterations (relative to m), the vector xn is already a good approximation to the exact solution.
Indeed, a theorem of Greenbaum, Pták and Strakoš states that for every nonincreasing sequence a1, ..., am−1, am = 0, one can find a matrix A such that the ‖rn‖ = an for all n, where rn is the residual defined above.
denote the smallest and largest eigenvalue of the matrix
where Pn denotes the set of polynomials of degree at most n with p(0) = 1, V is the matrix appearing in the spectral decomposition of A, and σ(A) is the spectrum of A.
Roughly speaking, this says that fast convergence occurs when the eigenvalues of A are clustered away from the origin and A is not too far from normality.
[5] All these inequalities bound only the residuals instead of the actual error, that is, the distance between the current iterate xn and the exact solution.
Therefore, the method is sometimes restarted after a number, say k, of iterations, with xk as initial guess.
The shortcomings of GMRES and restarted GMRES are addressed by the recycling of Krylov subspace in the GCRO type methods such as GCROT and GCRODR.
[6] Recycling of Krylov subspaces in GMRES can also speed up convergence when sequences of linear systems need to be solved.
Unlike the unsymmetric case, the MinRes method is given by a three-term recurrence relation.
It can be shown that there is no Krylov subspace method for general matrices, which is given by a short recurrence relation and yet minimizes the norms of the residuals, as GMRES does.
These also work with a three-term recurrence relation (hence, without optimality) and they can even terminate prematurely without achieving convergence.
The idea behind these methods is to choose the generating polynomials of the iteration sequence suitably.
Therefore, multiple solvers are tried in practice to see which one is the best for a given problem.
is an (n + 1)-by-n matrix, hence it gives an over-constrained linear system of n+1 equations for n unknowns.
The QR decomposition can be updated cheaply from one iteration to the next, because the Hessenberg matrices differ only by a row of zeros and a column:
where hn+1 = (h1,n+1, ..., hn+1,n+1)T. This implies that premultiplying the Hessenberg matrix with Ωn, augmented with zeroes and a row with multiplicative identity, yields almost a triangular matrix:
Given the QR decomposition, the minimization problem is easily solved by noting that