# Inner iterations in the preconditioned conjugate gradient method

As shown in Algorithm 2 of this document a linear system $$M{\bf z}_k = {\bf r}_k$$ is required for every iteration of the preconditioned conjugate gradient (PCG) method. I assume this system is typically solved using the (un-preconditioned) conjugate gradient method. If this is the case, why does this approach not have a significant negative impact of PCG method? Is it that a linear system formed by the preconditioner $$M$$ converges very quickly? Or is the inner iteration solved to a lesser tolerance?

Clarification

I am looking to solve a large (matrix free) saddle-point system.

• If you use a Jacobi preconditioner you can evaluate this directly, if you use a Gauss-Seidel or SOR preconditioner it is also clear how to evaluate this. There are also polynomial preconditioners which just require a few steps. Other preconditioners include incomplete Cholesky, domain decomposition, and multigrid. Afaik you can use CG iterations within both domain decomposition and within multigrid, so ultimately it depends on what you preconditioner is. You should clarify this in order to get a more specific answer. Dec 19, 2023 at 20:46
• Do these techniques apply to large/matrix-free systems? Dec 19, 2023 at 23:48
• If you know the diagonal of the matrix then Jacobi is applicable, domain decomposition and multigrid are also applicable for matrix-free approaches, but ultimately it depends on the specific of the problem. That is, your clarification is too unspecific. Dec 20, 2023 at 9:12
• @lightxbulb I haven't studied those methods. I will do so. (I am self-teaching.) Dec 22, 2023 at 0:24

In practice, $$M$$ is defined in a way so that evaluating $$M^{-1}\mathbf r_k$$ is cheap, whereas computing the product with $$M$$ itself is typically neither convenient nor necessary. In other words, the preconditioner is defined by specifying what $$M^{-1}$$ is, not what $$M$$ is, and consequently, solving the linear system you state is trivial.
• @Olumide People use different notation. Some people prefer to denote the application of a preconditioner by $P$, others by $P^{-1}$. This is not specific to whether the linear system has a particular structure (e.g., saddle point problems), but just personal preference. Dec 20, 2023 at 17:23