Tag Info

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.