Refers to the (G)eneral (M)inimal (RES)idual algorithm, which is a popular Krylov subspace method for solving linear systems.

Assume a linear system of the form: $$Ax=b$$ where A is square and nonsingular.

GMRES is an iterative Krylov subspace method that solves linear systems. GMRES does not require the system matrix $A$ to be symmetric positive definite (as Conjugate Gradient does) or even symmetric (as MINRES does). GMRES is guaranteed not to break down as long as $A$ is invertible.

For a given $x$, define the residual vector $r(x)$ as $ r(x) = b - Ax$.

Let $x_0$ be the initial solution (typically is the zero vector if no information is known about the solution). Define $r_0 = r(x_0)$

GMRES selects iterates by choosing $x_k$ that solve the least squares problem

\begin{align*} \min & \| r(x) \|_2 \\ & \text{s.t. } x = x_0 + v, v \in \text{span} \lbrace r_0, Ar_0, \ldots A^{k-1} r_0 \rbrace \end{align*}

that is, by minimizing $\ell^2$ norm of the residual over a $k$-dimensional Krylov subspace.

Seminal paper: https://web.stanford.edu/class/cme324/saad-schultz.pdf

Other resource: https://en.wikipedia.org/wiki/Generalized_minimal_residual_method

history | excerpt history