Parallelizing and De-parallelizing Elimination Orders

摘要

The order in which the variables of a linear system are processed determines the total amounts of fill and work to perform LU decomposition on the system. We identify a trade off between the amounts of fill and work for a given order and the parallelism inherent in that order. We present two algorithms: one that tries to parallelize sequential orders, and another that tries to produce low fill orders, while, in the process, producing somewhat sequential orders. 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.