9

Consider the situation where you want to solve a linear system using a preconditioned Krylov method, but applying the preconditioner itself involves solving an auxiliary system, which is done with another preconditioned Krylov method.

  • On one extreme, you could run the inner solve to convergence within each step of the outer solve.

  • On the other extreme, you could not do the inner solve at all, but instead replace it with the inner preconditioner.

  • Somewhere in the middle, you could truncate the inner Krylov loop after some fixed number of iterations, or after a certain tolerance is achieved.

Empirically, I have come across situations where the first extreme is better, and different situations where the second extreme is better (in terms of total cost). However, I can find no clear reason why certain situations favor one strategy over another.

Is there any guidance or theory about when these different strategies are preferable?

Nick Alger
  • 3,143
  • 15
  • 25
  • 4
    For at least the third (intermediate) situation in your list, a good place to start might be Simoncini and Szyld, Flexible Inner-Outer Krylov Subspace Methods, SIAM J. Numer. Anal. 40 pp. 2219-2239. – Andrew T. Barker Jan 10 '15 at 18:03
  • Thanks for the reference, I'm curious to see what they have there. Strangely, in practice I have found doing different forms of the intermediate situation to give by far the worst performance. If the tolerance/iteration number is fixed, the outer solver tends to hang at the error level of the inner tolerance. Starting with a large inner tolerance and decreasing it as the outer method progresses also seems to perform worse than just setting the inner tolerance small to begin with. – Nick Alger Jan 14 '15 at 12:20
  • Are you using flexible Krylov methods? The results you describe are what I'd expect if you were not. The intermediate situation is exactly the one where the preconditioner is (slightly) different at each iteration, which is when flexible Krylov methods are required. – Andrew T. Barker Feb 06 '15 at 04:19

1 Answers1

1

This question has been open for a long time, but I think it still deserves to be answered.

The fundamental problem with the use of Krylov-space solvers on individual blocks as inner preconditioners is that they are not linear operators. To understand this, let's denote by $\tilde x = K(A,P,\tau,N; b)$ the vector you get as a solution by running a Krylov space method $K$ on the linear system $Ax=b$ for at most $N$ iterations or until a tolerance $\tau$ is reached, using a preconditioner $P\approx A^{-1}$. In other words, you can think of $K$ as an operator that acts on $b$.

Now note that $K(A,P,0,\infty;\cdot)$ is a linear operator: it would require solving $Ax=b$ exactly, i.e., $K(A,P,0,\infty;b)=A^{-1}b$, which is linear in $b$. In many cases, running a Krylov space method for exactly one iteration starting from a zero vector is also a linear operator applied to $b$. But because the sequence of Krylov vectors depends on the starting residual $r^{(0)}=b-Ax^{(0)}$, the operator $K(A,P,\tau,N; \cdot)$ is in general not a linear operator for finite $N$ and $\tau$.

What this means is that if you use $K(A,P,\tau,N; \cdot)$ as part of a preconditioner for a linear system in which $A$ is one block, then you end up with a preconditioner that does not act as a linear operator.

This is in contrast to many other methods that are used to precondition: for example, one SSOR step is a linear operation on the vector to which you apply it, as are all other methods that apply one step of a fixed point iteration.

The fundamental problem now is that most Krylov space methods do require that the preconditioner is a linear operator. They will simply not converge if the preconditioner is not linear, explaining your observation. On the other hand, there are variations of some Krylov space methods -- typically prefixed by the word "Flexible", such as F-GMRES in "Flexible GMRES" -- that work around this and that can deal with preconditioners that are not linear operators. These flexible variants of the original methods will still converge, and are often powerful methods when coupled with good (but nonlinear) preconditioners.

Wolfgang Bangerth
  • 55,373
  • 59
  • 119