# RCM better than Nested dissection? (For FEM discretizations in 2D and 3D)

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 :)

• How are you measuring fill-in? What do you mean when you say "outperform"? May 25 at 23:05
• 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.
– bobo
May 25 at 23:49
• 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. May 26 at 1:43
• 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?
– bobo
May 26 at 8:01
• What is RCM? Reverse Cuthill-McKee? You might want to explain the acronym in the question. May 26 at 15:11