Multigrid on "not perfectly rectangular" grid

Question

Multigrid introductions normally use a rectangular grid. Interpolation of values is then straight forward: Just interpolate linearly on the edge between two adjacent nodes of the coarse grid to find the value of the fine grid node on that edge.

For an FEM application I have a grid which is "topologically" rectangular so that node connections are as on a rectangular grid. However, the nodes are not perfectly aligned on a grid but may travel small distances in order to better fit the geometry, while still maintaing connections as in a perfect rectangular grid.

The mesh looks something like that: Mesh example. You see: Connections are "regular rectangular", but node positions not.

I can image several "reasonable" geometric interpolation schemes für such a setting.

The general question is: Does multigrid require a perfectly aligned rectangular grid, or will it also work with the situation described above, as long as the interpolation is "good"? Or is it better to use algebraic multigrid in that case? (Which I don't prefer since it's not that intuitive as geometric multigrid.)

Answer 1

Multigrid doesn't need a Cartesian (rectangular), uniform grid. What it needs is that you can define a fine and a coarse level (possibly recursively, if you want to go from a two-level to a multi-level scheme), and that you can define interpolation operators between these levels. The easiest way to explain this is if you indeed have a Cartesian grid, but you can in fact start with any coarse mesh, refine it once, and just like this: you have a finer mesh.

In other words, it is easiest to think of multigrid-suitable meshes not as a fine mesh and how to find the coarser meshes, but to start with a coarse mesh from which you get the finer levels by uniform refinement (i.e., every quadrilateral is subdivided into four smaller ones). Since uniform refinement is always possible, this readily gives you a hierarchy. This is opposed to coarsening, which is not always possible if you are just given an particular mesh, and so makes defining a mesh hierarchy much more complicated. (Which is why people have come up with algebraic multigrid methods to define the coarse levels based just on the matrix, without thinking of the underlying mesh from which it was created.)

Answer 2

Lets say that you have the following grid composed of rectangular elements:

Now if you perform your interpolation assuming a normal structured rectangular grid then you will be introducing errors associated with this inaccurate interpolation. In other words when you restrict your residual vector and when you prolong your error vector there will be errors from the interpolation.

Now if your grid is "close" to being a normal structured cartesian grid then this may work, at least at first, but I suspect one of two things will happen depending on how far off you grid is from being rectangular:

1) You might find that the multigrid begins to converge at first. After all initially your error is large anyways and your "approximate" interpolation really just means that some nodes are slightly over represented while some are slightly under respresented. However you may find that the convergence stagnates as the solution becomes more accurate and the interpolation errors become more important.

2)Another possibility is that the multigrid does end up converging, but not as fast as it should if you had used the correct interpolation.

Basically by being off with your interpolation you are weighting the importance of certain nodes inaccurately. For example in 2D if you are weighting a given node as:

\begin{bmatrix} 0.25 & 0.5 & 0.25 \\ 0.5 & 1.0 & 0.5 \\ 0.25 & 0.5 & 0.25 \end{bmatrix}

when in truth because your grid is not exactly cartesian it should be:

\begin{bmatrix} 0.25 & 0.55 & 0.25 \\ 0.55 & 1.0 & 0.49 \\ 0.28 & 0.52 & 0.30 \end{bmatrix}

then this will result in some error. Whether this error prevents convegence will likely depend on how far off your grid is from being cartesian.

While AMG is more difficult to understand/implement it sounds like it is the correct method for your grid. Applying geometric multigrid to an "approximate" rectangular grid may work, but I would guess that it is a band-aid solution at best. Hope this helps.

Update: I think there may have been some confusion in my answer. I am not saying that geometric multigrid will only work with cartesian meshes, but rather that defining interpolation (and hence restriction) on cartesian meshes is easy whereas on non-structured meshes this may be difficult. For example consider the case of even a simple 2D domain with a triangular mesh. Refining this mesh is easy - at least conceptually - but how would you define an interpolation operator between the coarse and fine mesh? I prefer AMG simply because it performs more like a "black box" solver, i.e. doesnt need information on the underying mesh, however this is just my person bias/quirk. Geometric multigrid can work as long as you can provide accurate interpolation operators.