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?


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

  • 2
    $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Commented Dec 19, 2023 at 20:46
  • $\begingroup$ Do these techniques apply to large/matrix-free systems? $\endgroup$
    – Olumide
    Commented Dec 19, 2023 at 23:48
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Commented Dec 20, 2023 at 9:12
  • $\begingroup$ @lightxbulb I haven't studied those methods. I will do so. (I am self-teaching.) $\endgroup$
    – Olumide
    Commented Dec 22, 2023 at 0:24

1 Answer 1


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.

  • $\begingroup$ Unless I am mistaken this does not appear to be always the case in saddle-point systems e.g (10.16) here $\endgroup$
    – Olumide
    Commented Dec 19, 2023 at 23:46
  • $\begingroup$ @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. $\endgroup$ Commented Dec 20, 2023 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.