## § Krylov subspace method

This is a class of methods used to solve $Ax = b$, where $A$ is sparse. Krylov subspace methods are a class of methods which use the idea of a Krylov subspace. There is conjugate gradient (CG), GMRES (Generalized minimal residual method).
$K_m(A, v) \equiv span \{ v, Av, A^2v, \dots, A^m v\}$
Clearly, $K_m \subseteq K_{m+1}$, and there is a maximum $K_N$ that we can span (the full vector space). We are interested in the smallest index $M$ such that $K_M = K_{M+1}$. We notice that $K_M$ is invariant under the action of $A$. Now, let's consider:
\begin{aligned} K_m(A, x) &\equiv span \{x, Ax, A^2x, \dots A^m x \} \\ &= span \{ A^{-1} b, b, Ab, \dots A^{m-1} x \} \qquad \text{(substitute x = A^{-1}b)} \\ &= A span \{ A^{-1} b, b, Ab, \dots A^{m-1} b\} \qquad \text{(Invariance of Krylov subspace)} \\ &= span \{b, Ab, \dots A^m b\} \\ &= K_m(A, b) \end{aligned}
We learnt that $Ax = b$ has a solution in $K_m(A, b)$. Using this, we can build solvers that exploit the Krylov subspace. We will describe GMRES and CG.

### § Generalized minimal residual --- GMRES

We wish to solve $Ax = b$ where $A$ is sparse and $b$ is normalized. The $n$th Krylov subspace is $K_n(A, b) \equiv span~\{b, Ab, A^2b, \dots, A^nb \}$. We approximate the actual solution with a vector $x_n \in K_n(A, b)$. We define the residual as $r_n \equiv A x_n - b$.