Preconditioning a Krylov method with another Krylov method

Question

In methods like gmres or bicgstab it could be attractive to use another Krylov method as a preconditioner. After all they are easy to implement in a matrix-free way and in a parallel environment. For example, one could use a few (let say ~5) iterations of unpreconditioned bigcstab as a precontioner for gmres, or any other combination of Krylov methods.

I do not find much reference to such approach in the literature, so I expect that this is because it is not very effective. I would like to understand why it is not efficient. Are there cases where it is a good choice?

In my research, I am interested about the solution of 3-D elliptic problems in a parallel (MPI) environment.

Answer 1

Interesting that this question came yesterday, since I just finished an implementation yesterday that does this.

My Background

Just to start of, let me know that while my education background is from scientific computing, all work I have done since graduating, including my current Ph.D. work, has been in computational electromagnetics. So, I guess our backgrounds are somewhat similar, since you also appear to be looking at physics (based on your profile).

FGMRES

First of all, what you are looking for, as Guido Kanschat has already mentioned in a comment, is called Flexible GMRES or FGMRES. The reference, including pseudocode, is in [1]. While I sometimes find numerical SIAM papers a bit hard to read, [1] (and most of Saad's other work, including the brilliant [B1], apparently legally available for free online) is different; the paper is a fascinating read, very clearly written and with a few nice examples and suggestions for applications.

FGMRES is easy to implement, particularly if you already have a working RIGHT preconditioned GMRES. Note the keyword RIGHT here - if you have a LEFT preconditioned GMRES, i.e. you are used to solving MAx=Mb, then you have to make a few modifications. Compare [B1,Algorithm 9.4 on pg. 282] to [B1,Algorithm 9.5,pg. 284]. You can also find the FGMRES in [B1,Algorithm 9.6, pg. 287], but I would really encourage you to read [1] as it is short, well written and still has many interesting details.

What does it do

FGMRES basically allows you to switch preconditioners for every iteration, if you wish. One of the applications for this is that you can use some preconditioner that works very well when you are far away from the solution, and then switch to another one when you get closer. [2], which I have not read in detail, appears to discuss something similar to this.

However, the most interesting application in my case was that you could use a (preconditioned) GMRES as a preconditioner for your FGMRES. This is the reason behind the typical name for FGMRES, "inner-outer GMRES". Here, "outer" refers to the FGMRES solver, which (as preconditioner) uses an "inner" solver.

So, how good is this in practice?

In my case, this worked absolutely brilliant. In the inner loop, I "solve" a reduced-complexity formulation of my problem. On its own, this solution is far too inaccurate for our use, but it works absolutely great as a preconditioner. Note the "" around "solve" - there is no need to run the inner solver to convergence, since you are only looking for rough approximations. In my case, I went from using 151 iterations, each costing 64 seconds, to 72 iterations, each costing 79 seconds (I used a fixed 5 iterations in the inner GMRES). That is a total saving of an hour, with no loss of accuracy and very little coding work since we already had a functioning GMRES which we just made recursive.

For some applications of this stuff, demonstrating the potential performance, see [3] (which actually uses a three-level FGMRES, so FGMRES, with FGMRES as inner, with GMRES as inner-inner) and [4], which might be too application specific for your use, but contains several interesting test cases.

References

[1] Y. Saad, “A flexible inner-outer preconditioned GMRES algorithm,” SIAM J. Sci. Comp., vol. 14, no. 2, pp. 461–469, Mar. 1993. http://www-users.cs.umn.edu/~saad/PDF/umsi-91-279.pdf

[2] D.-Z. Ding, R.-S. Chen, and Z. Fan, “SSOR preconditioned inner-outer flexible GMRES method for MLFMM analysis of scattering of open objects,” Progress In Electromagnetics Research, vol. 89, pp. 339–357, 2009. http://www.jpier.org/PIER/pier89/22.08112601.pdf

[3] T. F. Eibert, “Some scattering results computed by surface-integral-equation and hybrid finite-element-boundary-integral techniques, accelerated by the multilevel fast multipole method,” IEEE Antennas and Propagation Magazine, vol. 49, no. 2, pp. 61–69, 2007.

[4] Ö. Ergül, T. Malas, and L. Gürel, “Solutions of Large-Scale Electromagnetics Problems using an Iterative Inner-Outer Scheme with Ordinary and Approximate Multilevel Fast Multipole Algorithms,” Progress In Electromagnetics Research, vol. 106, pp. 203–223, 2010. http://www.jpier.org/PIER/pier106/13.10061711.pdf

[B1] Y. Saad, Iterative Methods for Sparse Linear Systems. SIAM, 2003. http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf

Answer 2

Such a nested Krylov subspace method may work quite well in practice. It may be of interest for non symmetric linear systems for which restarted GMRES stagnates and unrestarted GMRES is too expensive or uses too much memory. Some literature:

1. GMRESR: A family of nested GMRES methods, van der Vorst, Vuik
2. Flexible inner-outer Krylov subspace methods, Simoncini, Szyld
3. A flexible inner-outer preconditioned GMRES algorithm, Saad
4. Further experiences with GMRESR, Vuik