- Parallel Gaussian Elimination with Linear
Work and Fill. C. Bornstein, B. Maggs, G. Miller, and R. Ravi.
Proceedings of the 38th Annual Symposium on Foundations of Computer
Science (FOCS), October 1997, pp. 274-283.
- This paper presents an algorithm for finding parallel
elimination orderings for Gaussian elimination. Viewing a system of
equations as a graph, the algorithm can be applied directly to
interval graphs and chordal graphs. For general graphs, the algorithm
can be used to parallelize the ordering produced by some other
heuristic such as minimum degree. In this case, the algorithm is
applied to the chordal completion that the heuristic generates from
the input graph. In general, the input to the algorithm is a chordal
graph G with n nodes and m edges. The algorithm produces an
ordering with height at most O(log^3 n) times optimal, fill at most
O(m), and work at most O(W*(G)), where W*(G) is the minimum possible
work over all elimination orderings for G. Experimental results show
that when applied after some other heuristic, the increase in work and
fill is usually small. In some instances the algorithm obtains an
ordering that is actually better, in terms of work and fill, than the
original one. We also present an algorithm that produces an ordering
with a factor of log n less height, but with a factor of O(sqrt(log
n)) more fill.
- Back to other
- Back to my home page