Claudson Ferriera Bornstein

Parallelizing and De-parallelizing Elimination Orders Degree Type: Ph.D. in Computer Science
Advisor(s): Bruce Maggs, Gary Miller
Graduated: August 1998

Abstract:

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.

Thesis Committee:
Bruce M. Maggs (Co-chair)
Gary L. Miller (Co-chair)
R. Ravi
John Gilbert (Xerox Parc)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Keywords: Parallel elimination orders, fill and work minimization, nested dissection, min- degree, hybrid algorithms, chordal completion, LU decomposition, Gaussian elimination, chordal graphs, interval graphs, graph theory