Computer Science Department
School of Computer Science, Carnegie Mellon University
Parallelizing and De-parallelizing Elimination Orders
Claudson Ferreira Bornstein
The first algorithm takes a sequential order for a matrix and produces a parallel one with at most a constant factor more nonzeros and work. We also show that, for certain graphs, any parallel order requires an amount of additional fill that is a function of the amount of parallelism exhibited. The more parallel the order, the more fill it introduces.
We identified a particular "deficiency" of nested dissection that arises from the parallel nature of the orders it produces. Thus, when shifting our goal towards fill and work minimization, we choose to modify nested dissection to obtain a similar algorithm that produces orders that introduce less fill and work than a traditional nested dissection order would, but that are also less parallel than the orders that would be produced by the traditional nested dissection algorithm.
Our experimental work comparing this variant of nested dissection and a number of other publicly available ordering algorithms indicates that while a few of the algorithms produce comparable-quality orders, the minimum-degree algorithm stands out as the worst one. Contrary to common belief, the minimum-degree algorithm produces poor quality orders in terms of fill and work. Our variant of nested dissection compares favorably with state-of-the-art ordering algorithms, including implementations of nested dissection, minimum-degree and their hybrids.