# How to use grid sizes that are not powers of two in Geometric Multigrid

I am trying to solving a poisson equation in structured grid with Geometric Multigrid method. However, when coarsening the fine grid, I simply double the grid spacing at each successive level. That means that the number of points on the finest grid must be a power of 2. This is an undesirable constraint when doing some numerical simulations.

Is there any strategy to avoid this constraint (i.e., to use grids whose sizes are not powers of 2?

Thanks.

• You can use any grid sizes you want in geometric multigrid, are you asking how to build the appropriate restriction and coarsening operators? – Aron Ahmadia Jul 5 '12 at 23:03
• Sorry, I mean the number of grid in some direction has to be the power of 2 in the method of GMG. If not the case, how to coarsen the grid. – Anyang Jul 7 '12 at 1:53
• scicomp is a collaborative edited wiki, and we will clean up grammar/math formatting errors as we encounter them in questions and answers. Please contact the moderators or system staff if you have any questions about this policy. Thanks. – Aron Ahmadia Jul 8 '12 at 18:34

## 2 Answers

All you need is a hierarchy of meshes that reduces sufficiently fast. You can use a 3:1 coarsening ratio, or you could use unstructured meshes, etc. There is no such restriction as the one you cite, even though it's common to implement the multigrid method with a 2:1 coarsening ratio.

• Yes, I can choose the the different ratio, but eventually the number of finest grid is also restricted. – Anyang Jul 7 '12 at 1:54
• I think the question is whether one can use arbitrary grid sizes; e.g., a prime number. – David Ketcheson Jul 7 '12 at 6:23
• @DavidKetcheson: You mean what do you do if you have a 5x5 mesh? You coarsen it to a 2x2 mesh where the four coarse mesh cells consists of 2x2, 2x3, 3x2 and 3x3 fine mesh cells, respectively. As I said, there is no real requirement on how to do the coarsening, it just needs to end up in a hierarchy of meshes. – Wolfgang Bangerth Jul 7 '12 at 11:36
• @JedBrown Following your strategy,I can get the coarse grid,in this case, I get a non-uniform grid size, therefore, how should I construct the Restriction and Interpolation operator? – Anyang Jul 9 '12 at 2:04
• @WolfgangBangerth I did not find a multigrid book at my hand covers the prolongation and restriction of non-uniform grid. Could you please give me an suggestion? – Anyang Jul 9 '12 at 14:16

Actually there's no restriction that the number of intervals in the fine grid should have to be a power of 2. This number can be either odd or even. No big deal. Take 1-dimension problem as an example, suppose the number of intervals in the fine grid is 7(Thus the number of nodes is 8), then you can use the following restriction operator

Columns 1 through 7

      0.5         0.25            0            0            0            0            0
0         0.25          0.5         0.25            0            0            0
0            0            0         0.25          0.5         0.25            0
0            0            0            0            0         0.25          0.5


Column 8

        0
0
0
0.25


If the number of intervals in the fine grid is 8(Thus the number of nodes is 9), then the restriction operator should be

Columns 1 through 7

      0.5         0.25            0            0            0            0            0
0         0.25          0.5         0.25            0            0            0
0            0            0         0.25          0.5         0.25            0
0            0            0            0            0         0.25          0.5
0            0            0            0            0            0            0


Columns 8 through 9

        0            0
0            0
0            0
0.25            0
0.25          0.5


So you see, whether the number of intervals in the fine grid is odd or even, the multigrid technique would work well.

• The first and last rows of your restriction operator do not sum to 1 -- is that okay? Or should they be scaled so that they sum to 1? Moreover, will the prolongation operator be a constant multiple of the transpose of the restriction operator, or will the first and last rows need to be multiplied by a different constant than the rest of the transposed restriction operator matrix? – nukeguy Jun 7 '16 at 19:58
• I just realized that the sums of the rows of the restriction operators are irrelevant in a multigrid scheme. You can multiply the restriction operator by any invertible matrix and it won't change anything. Likewise, the sums of the columns of an interpolation operator are also irrelevant. – nukeguy Jul 20 '17 at 19:57