Reducing the Height of an Elimination Tree Through Local Reorderings
Finding low elimination trees is important in parallel Cholesky factorization.
We look at two orderings for achieving low height, Nested Dissection and
Maximal Independent Subset, and show that in general they will not give
a minimum height elimination tree. A more general version of Nested Dissection
called Minimal Cutset orderings is shown to always contain an ordering
that gives a minimum height elimination tree for an arbitrary graph. From
this we design the Minimal Cutset algorithm for reducing the height of
a given elimination tree. This algorithm is compared with an algorithm
using tree rotations by Liu and an algorithm that reorders chains by Hafsteinsson.
We show that none of the three algorithms is strictly better than any of
the other. Finally we show that all three algorithms are members of a more
general class of algorithms that depend on a common result on how elimination
trees can be restructured.