15
$\begingroup$

I wonder what has happened to polynomial preconditioners. I am interested in them, because they appear to be comparatively elegant from a mathematical perspective, but as far as I have read in surveys on krylov methods, they generally perform very poor as preconditioners. In the words of Saad and van der Host, "Current interest in these techniques has all but vanished" (Here). Nevertheless, there have been uses for multicore- and GPU-calculations in the recent past.

Can anyone tell me or rather explain me in which contexts these methods are still alive, and where to find a good survey on the current state of the art?

Improve this question
$\endgroup$
1
  • $\begingroup$ A recent paper on the arxiv (arxiv.org/pdf/1806.08020.pdf) investigates polynomial preconditioners for Arnoldi. In particular, they test it on a variety of problems and get good speed-up. They conclude that the reduction in vector operations due to polynomial preconditioning "holds great promise for communication-avoiding eigenvalue computation on high performance computers". I am not one of the authors. $\endgroup$
    – amarney
    Jul 10 '18 at 19:58
12
$\begingroup$

To perform reasonably, polynomial preconditioners need fairly accurate spectral estimates. For ill-conditioned elliptic problems the smallest eigenvalues are usually separated such that methods like Chebyshev are far from optimal. The most interesting property of polynomial methods is that they do not require any inner products.

It's actually quite popular to use polynomial smoothers in multigrid. The main difference from a preconditioner is that the smoother is only supposed to target part of the spectrum. A polynomial smoother is currently the default in PETSc's multigrid, for example. See also Adams et al, Parallel multigrid smoother: polynomial versus Gauss-Seidel (2003) for a comparison.

Polynomial preconditioners can be used purely to reduce the frequency of reductions. Although they have to be retuned for each matrix, the savings can be significant on hardware in which reductions are expensive (common on large supercomputers). See McInnes, Smith, Zhang, and Mills, Hierarchical and Nested Krylov Methods for Extreme-Scale Computing (2012) for more on this.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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