1
$\begingroup$

I realize this might be a too general question but here goes nothing:

I am trying different re-ordering strategies and checking the fill-in of $A=LU$.

I have 2D ($p=1$, $h=1/40$ on $\Omega = [-1,1]^2$) discretizations of the Helmholtz equation and I was genuinely surprised to see Reverse Cuthill-McKee (RCM) outperform Nested dissection in all cases that I tried out.

Now, I was left in the belief that Nested dissection is state of the art. What am I missing? Does the strength of Nested Dissection lie in the hierarchical elimination using multifrontal methods? Is it 2D vs 3D? Or is RCM actually better?

I am grateful for any tips/pointers/directions and answers :)

Improve this question
$\endgroup$
6
  • $\begingroup$ How are you measuring fill-in? What do you mean when you say "outperform"? $\endgroup$
    – Bill Greene
    May 25, 2021 at 23:05
  • $\begingroup$ I am simply checking the number of non-zero entries in the factors $L$ and $U$. It seems to me that nested dissection actually concentrates the fill-in to some regions, rather than reduce it. $\endgroup$
    – bobo
    May 25, 2021 at 23:49
  • $\begingroup$ Neither of them are guaranteed to reduce the bandwidth of the matrix (i.e. there are counter-examples). Using the bandwidth as the measure of fill-in (since L and U will have non-zeros only inside the band), we can say that neither of them has a theoretical edge over the other. However, in my experience, for FEM matrices, nested dissection hardly reduces the bandwidth while RCM generally reduces it. $\endgroup$
    – Abdullah Ali Sivas
    May 26, 2021 at 1:43
  • $\begingroup$ Thank you, that makes sense. The goal with nested dissection seems to be to generate an arrowhead shape, which concentrates the fill-in near the end of the matrix so I would not expect it to reduce bandwidth. Is it possible that perhaps measuring fill-in using the $LU$ factors is the wrong approach? $\endgroup$
    – bobo
    May 26, 2021 at 8:01
  • 1
    $\begingroup$ What is RCM? Reverse Cuthill-McKee? You might want to explain the acronym in the question. $\endgroup$
    – Wolfgang Bangerth
    May 26, 2021 at 15:11

1 Answer 1

Reset to default
3
$\begingroup$

This landmark paper by George proves that a nested dissection ordering of a regular, four-node element, finite element mesh produces minimum fill-in.

Although it is straightforward to produce such an ordering by inspection, the graph algorithms that attempt to do this for a general sparse structure only approximate this ordering.

Assuming you are obtaining your nested dissection ordering by one of these algorithms, I suggested you take a look for small meshes and see how close it comes to the true nested dissection ordering.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for this comment! I was aware of the paper but I had somehow forgotten that there was this proof. In fact, that is probably why I was left in this impression. My algorithm is very similar to the ones in the paper as it is based on geometric considerations but it seems that already adding a boundary will result in a loss of the fill-in minimizing property. $\endgroup$
    – bobo
    May 26, 2021 at 11:59
  • $\begingroup$ in fact, it seems that nested dissection is useful beyond minimising fill-in, as it also allows to manage the fill-in (Such as in multifrontal methods). Is this correct? $\endgroup$
    – bobo
    May 26, 2021 at 12:00

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.