Editing Conjugate gradient method (section)

=== Using the preconditioner in practice ===
It is important to keep in mind that we don't want to invert the matrix <math>\mathbf{M}</math> explicitly in order to get <math>\mathbf{M}^{-1}</math> for use it in the process, since inverting <math>\mathbf{M}</math> would take more time/computational resources than solving the conjugate gradient algorithm itself. As an example, let's say that we are using a preconditioner coming from incomplete Cholesky factorization. The resulting matrix is the lower triangular matrix <math>\mathbf{L}</math>, and the preconditioner matrix is:

<math>\mathbf{M}=\mathbf{LL}^\mathsf{T}</math>

Then we have to solve:

<math>\mathbf{Mz}=\mathbf{r}</math>

<math>\mathbf{z}=\mathbf{M}^{-1}\mathbf{r}</math>

But:

<math>\mathbf{M}^{-1}=(\mathbf{L}^{-1})^\mathsf{T}\mathbf{L}^{-1}</math>

Then:

<math>\mathbf{z}=(\mathbf{L}^{-1})^\mathsf{T}\mathbf{L}^{-1}\mathbf{r}</math>

Let's take an intermediary vector <math>\mathbf{a}</math>:

<math>\mathbf{a}=\mathbf{L}^{-1}\mathbf{r}</math>

<math>\mathbf{r}=\mathbf{L}\mathbf{a}</math>

Since <math>\mathbf{r}</math> and <math>\mathbf{L}</math> and known, and <math>\mathbf{L}</math> is lower triangular, solving for <math>\mathbf{a}</math> is easy and computationally cheap by using [[Triangular matrix#Forward and back substitution|forward substitution]]. Then, we substitute <math>\mathbf{a}</math> in the original equation:

<math>\mathbf{z}=(\mathbf{L}^{-1})^\mathsf{T}\mathbf{a}</math>

<math>\mathbf{a}=\mathbf{L}^\mathsf{T}\mathbf{z}</math>

Since <math>\mathbf{a}</math> and <math>\mathbf{L}^\mathsf{T}</math> are known, and <math>\mathbf{L}^\mathsf{T}</math> is upper triangular, solving for <math>\mathbf{z}</math> is easy and computationally cheap by using [[Triangular matrix#Forward and back substitution|backward substitution]].

Using this method, there is no need to invert <math>\mathbf{M}</math> or <math>\mathbf{L}</math> explicitly at all, and we still obtain <math>\mathbf{z}</math>.