# Generalized Minimum Residual Method

**Introduction**

The Generalized Minimum Residual Method (GMRES) is an algorithm to compute an approximate solution to a linear system of equations of the form

$$A \cdot x = b$$

where A is usually a sparse matrix. It is a Krylov-subspace projection method that finds a minimises the residual norm to find an approximate solution to the system of equations. The complete theory is beyond the scope of this website and will only be introduced very briefly. For further reading, please refer to [Saad (2003)](../literature).

**Projection Methods**

Projection methods usually use a a series of projection operators to derive a approximate solution $\tilde{x}$ from a subspace of lower dimension. They are defined by the condition, that the residual of the system has to be orthogonal to $m$ indepent directions and can be described as

$$\text{Find} \, \tilde{x} \in x_0 + \mathcal{K}, \quad \text{such that} \, b - A \tilde{x} \perp \mathcal{L}$$

with $A \in \mathcal{R}^{n \times n}$, $x_0 \in \mathcal{R}^{n}$ the initial guess vector and $\mathcal{K}, \mathcal{L} \subset \mathcal{R}^{n}$ [(Saad, 2003)](../literature) the subspaces of the residual and the orthogonality constraints. The projection is chosen such, that the solution vector is in the subspace $\mathcal{K}$ and orthogonal to the subspace $\mathcal{L}$. The dimension of the subspaces is $m$ with $\mathcal{K}$ describing the degrees of freedom and $\mathcal{L}$ the constraints.

**Krylov-subspace methods**

These are methods that use a specific class of subspaces as their $\mathcal{K}$ subspace, the Krylov-subspace. It is defined as

$$\mathcal{K}_m \left(A, r_0\right) = span \left\{r_0, A r_0, A^2 r_0,..., A^m r_0\right\}$$

with $r_0 = b - A x_0$ being the residual vector and $A \in \mathcal{R}^{n \times n}$, $x_0 \in \mathcal{R}^n$ [(Saad, 2003)](../literature). There exist different methods within this category, some examples being the Conjugate Gradient method, Biconjugate Gradient method and the GMRES Method [(Ferziger et al., 2020)](../literature). The differences are in the definition of the subspaces $\mathcal{K}$ and $\mathcal{L}$. In the case of the GMRES method the subspaces are choses as follows:

$$\mathcal{K} = \mathcal{K}_m \left(A, r_0\right)$$

$$\mathcal{L} = A \cdot \mathcal{K}_m \left(A, r_0\right).$$

**GMRES**

It can be shown, that the best approximate solution to the system of equations in a given Krylov subspace is expressed via

$$x_m = x_0 + V_m y_m$$

where $V_m$ is a matrix consisting of orthonormal column-vectors of the Krylov-subspace and $y_m$ is the vector that minimizes

$$y_m = \text{argmin}_{y} \left\Vert\beta e_1 - H_m y\right\Vert_{2}$$

with $\beta = \left\Vert r_0 \right\Vert$ and $H_m$ being an upper Hessenbergmatrix of dimension $(m+1)\times m$ [(Saad, 2003)](../literature).

Employing an Arnoldi-Gram-Schmidt or an Arnoldi-Householder$^{1}$ algorithm to find a set of orthonormal vectors of the Krylov-space, the Hessenberg matrix is build up. The minimizer can be calculated quickly by transforming the Hessenberg matrix through the application of $m$ rotation matrices into upper triangular form and using back-substitution. This process yields the current residual which can be compared against a set $\epsilon > 0$ as convergence criterion. If the desired $\epsilon$ is not reached, the algorithm can be restarted with $x_m$ as the new initial guess. The complete algorithm converges against the exact solution after at most $n$ steps for a non-singular matrix $A$ [(Saad, 2003)](../literature).

$^{1}$ The current implementation in the present code is the Arnoldi-Gram-Schmidt variation, but the Arnoldi-Householder veriation is preferred due to the lower build-up of numerical errors and will be used in the future.