17

As far as I am aware, multigrid solvers use iterative smoothers such as Jacobi, Gauss-Seidel, and SOR to dampen the error at various frequencies. Could a Krylov subspace method (like conjugate gradient, GMRES, etc.) be utilized instead? I don't think they are classified as "smootheners", but they can be used to approximate the coarse grid solution. Can we expect to see analogous convergence to the solution as we would in a standard multigrid method? Or is it problem dependent?

Paul
  • 12,045
  • 7
  • 56
  • 129

1 Answers1

19

Yes, you can, but Krylov methods generally do not have great smoothing properties. This is because they target the whole spectrum in an adaptive way that minimizes the residual or a suitable norm of the error. This will generally include some low frequency (long wavelength) modes that the coarse grids would have handled fine. Krylov smoothers also make the multigrid cycle nonlinear, so if multigrid is being used as a preconditioner for an outer Krylov method, the outer method should be "flexible" (e.g. GCR or FGMRES).

Using Krylov smoothers also greatly increases the number of dot products that must be computed, which becomes a significant bottleneck in parallel. However, even with these unattractive properties, Krylov smoothers are sometimes useful, especially for difficult problems in which good interpolation operators are not available.

A more popular alternative is to use polynomial smoothers (usually Chebyshev). These methods target a specified portion of the spectrum. For symmetric elliptic PDEs (where the discrete operator is symmetric positive definite or nearly so), it is common to estimate the largest eigenvalue $\lambda_\max$ of $D^{-1}A$ where $D^{-1}$ is the point-block Jacobi preconditioner for $A$ and target a range like $(0.1 \lambda_{\max}, 1.1 \lambda_{\max})$. Polynomial smoothers have no reductions and are linear operations (for any chose polynomial degree, usually chosen between $1$ and perhaps $5$). Usually a few iterations (say $5$ to $10$) of GMRES or CG are used to estimate $\lambda_\max$, so the user does not need to compute these themselves. The estimate of $\lambda_\max$ is also used by some algebraic multigrid methods to choose coarsening strategies.

Adams, Brezina, Hu, and Tuminaro (2003) is a nice paper on parallel and algorithmic performance of polynomial smoothers. Note that polynomial smoothers tend to be less effective (and/or difficult to formulate) for non-symmetric problems, in which case you will likely want to use Gauss-Seidel or more sophisticated (block/distributed) relaxation schemes.

Jed Brown
  • 25,650
  • 3
  • 72
  • 130
  • Can you suggest a good resource on polynomial and/or krylov smoothers? I've actually never heard of either :) – Paul Jan 17 '12 at 14:14
  • @JedBrown: Do you mean "elliptic" in the PDE or bilinear form sense (i.e., do you mean that all of the eigenvalues of the operator or principal symbol are positive?)? I am assuming the latter since you are talking about point-block Jacobi. – Jack Poulson Jan 17 '12 at 14:50
  • Paul I added a reference.

    @Jack Strictly speaking, the discrete operator should be SPD, but in practice, the methods tend to work as long as the spectrum is not too poorly distributed.

     – Jed Brown Jan 17 '12 at 15:17