7
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You can use any grid sizes you want in geometric multigrid, are you asking how to build the appropriate restriction and coarsening operators? $\endgroup$
    – Aron Ahmadia
    Jul 5, 2012 at 23:03
  • $\begingroup$ 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. $\endgroup$
    – Anyang
    Jul 7, 2012 at 1:53
  • $\begingroup$ 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. $\endgroup$
    – Aron Ahmadia
    Jul 8, 2012 at 18:34

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\begingroup$ Yes, I can choose the the different ratio, but eventually the number of finest grid is also restricted. $\endgroup$
    – Anyang
    Jul 7, 2012 at 1:54
  • 1
    $\begingroup$ I think the question is whether one can use arbitrary grid sizes; e.g., a prime number. $\endgroup$
    – David Ketcheson
    Jul 7, 2012 at 6:23
  • 1
    $\begingroup$ @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. $\endgroup$
    – Wolfgang Bangerth
    Jul 7, 2012 at 11:36
  • 1
    $\begingroup$ @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? $\endgroup$
    – Anyang
    Jul 9, 2012 at 2:04
  • 1
    $\begingroup$ @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? $\endgroup$
    – Anyang
    Jul 9, 2012 at 14:16
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – nukeguy
    Jun 7, 2016 at 19:58
  • $\begingroup$ 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. $\endgroup$
    – nukeguy
    Jul 20, 2017 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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