§ Krylov subspace method
This is a class of methods used to solve , where 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
Clearly, , and there is a maximum that we can span
(the full vector space). We are interested in the smallest index
such that .
We notice that is invariant under the action of .
Now, let's consider:
We learnt that has a solution in . 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 where is sparse and is normalized. The th
Krylov subspace is .
We approximate the actual solution with a vector . We
define the residual as .
§ Conjugate gradient descent