1

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.

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

1 Answers1

3

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.

Wolfgang Bangerth
  • 55,373
  • 59
  • 119
  • Unless I am mistaken this does not appear to be always the case in saddle-point systems e.g (10.16) here – Olumide Dec 19 '23 at 23:46
  • @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. – Wolfgang Bangerth Dec 20 '23 at 17:23