For which problems Krylov subspace methods are preferred over multigrid methods?

Question

As multigrid methods are known to have grid independent convergence rates with $O(N)$ computational cost, then why would one be interested in using Krylov subspace methods at all, for which convergence rates deteriorate with grid refinement? Are there any problems where Krylov solvers perform better than MG methods?

Answer 1

The answer depends somewhat on the discretization; for example, some boundary integral discretizations result in very well-conditioned matrices, for which a Krylov solver works just fine without having to introduce the multi-level machinery of multigrid.

For ill-conditioned matrices arising from finite difference or finite element methods, Krylov solvers are almost always paired with a preconditioner, for which multigrid methods can work very well.

Answer 2

This question is pretty well discussed in literature. However, there are lots of questions concerning multigrid on SciComp, so I decided to compose more or less detailed answer.

I. When multigrid DOES work fine as a stand–alone solver

MG works fine for rather simple elliptic problems. In fact, both MG and PCG (with MG cycles as inner iterations) usually give similar results for such problems in terms of iterations / working time and stay robust as you refine the mesh.

I solved diffusion–reaction 2D problem $$ -\epsilon \, \Delta u + u = f, \quad \mathbf x \in \Omega, \\ u|_{\Gamma_D} = g_D, \\ \left( \epsilon \, \nabla u \cdot \hat{\mathbf n} + u \right)|_{\Gamma_R} = g_R $$

with CATS’ PDEs on hierarchy of triangular meshes $\Omega_1 \subset \Omega_2 \subset \dots \subset \Omega_8$ of unit square with P1 FEs. I obtained the following results:

• $\text{MG(V)}$ and $\text{MG(W)}$ are V– / W–cycles as stand–alone solvers; $\mathbf P_{\text{MG(V)}}\text{CG}$ is preconditioned conjugate gradient with one V–cycle as an inner iteration; $\mathbf P_{\text{ILU(0)}}\text{CG}$ is preconditioned conjugate with incomplete $(\mathbf L + \mathbf I) \, \mathbf D \, (\mathbf I + \mathbf L^T)$ preconditioner (zero fill–in).
• I used 2 pre– and post–smoothing SSOR iterations inside MG–cycles.
• Numb of DOFs on the coarsest grid: 17; numb of DOFs on the finest grid: 656 897.
• In the table: “numb of iterations, $m$” / “solving time (in seconds), $t$.” I always started with a random initial guess $\mathbf x_0$ in order to introduce components of different frequencies in the initial error vector $(\mathbf x - \mathbf x_0)$; I stopped solving when $||\mathbf r_m||/||\mathbf r_0|| < 10^{-12}$.

Here’s comparison in terms of time $t$ as system size $n$ grows:

Indeed, you can see that $\text{MG}$ allows you to solve this problem in $O(n)$ time; so does $\mathbf P_{\text{MG}}\text{CG}$, but there is no difference between them in this case. I think this makes people ask questions like

As multigrid methods are known to have grid independent convergence rates with $O(n)$ computational cost, then why would one be interested in using Krylov subspace methods at all […]?

II. When multigrid DOES NOT work fine as a stand–alone solver

Consider the following cases.

II.1 More complex elliptic problems

It is usual to have jumping coefficients. For one, consider the following magnetostatic Poisson problem $$ \nabla \cdot \left( \frac{1}{\hat{\mu}} \, \nabla A_z \right) = \mu_0 \, J_z. $$

It is natural to have different values for magnetic permeability $\hat{\mu}$ for a magnet (gray box on the picture above) and air; current density $J_z$ is only nonzero within wires (red and blue squares on the picture above).

MG as a stand–alone solver loses its robustness (or even diverges) with respect to jump sizes for such problems, although the configuration is very simple. However, it still works nice as a preconditioner for Krylov solvers. If I have some free time, I will add a similar table for this problem.

There are lots of simple elliptic problems for which MG does not work. It is useful to look through a paper I mentioned in this answer in order to get a deeper understanding.

II.2 “Real–life” problems

Complex real–life problems involve different physics, several unknown fields and so forth. From the algebraic point of view it usually means block structure of the resulting (non-)linear systems. (Consider, for one, Stokes or Oseen problems, fluid–structure–interaction models typical for haemodynamics, thermoelasticity etc.)

It turns out that MG is in general a poor choice for such kind of problems. However, these problems usually “contain” some kind of “diffusion” (read: elliptic / Laplace blocks in the matrix), and one usually keeps this in mind while constructing preconditioners. Indeed, one often uses some kind of MG–cycles to approximate actions of inverses of elliptic blocks. One example I mentioned in this answer.

In order to get a better understanding, it is useful to check this lecture by @wolfgang-bangerth.

Answer 3

There are multiple answers to your question.

For one, as others have said, multigrid (MG) and krylov based solvers can work really well together, so this is a good reason to still use krylov solvers.

A second good reason to use krylov solvers is if the matrix to be inverted is ill conditioned ( for example due to discontinuous material properties ). In this case, MG does not guarantee convergence whereas Congugate Gradient method (e.g.) will.