Parallelizing Elimination Orders with Linear Fill

This paper presents an algorithm for finding parallel elimination orders 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 order 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 order with height at most O(log/sup 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 orders 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 order that is actually better, in terms of work and fill, than the original one. We also present an algorithm that produces an order with a factor of log n less height, but with a factor of O(/spl radic/log n) more fill.

Authors

• Claudson F. Bornstein
• Bruce M. Maggs
• Gary L. Miller
• R. Ravi 0001

Keywords

• Equations
• Contracts
• Particle separators
• Sparse matrices
• Concurrent computing
• Computer industry
• National electric code
• Sun
• Engineering profession
• Government
• Parallelization
• Heuristic
• System Of Equations
• Input Graph
• Gaussian Elimination
• Sequential Order
• Steps Of Algorithm
• Constant Factor
• Decrease In Potential
• Subtree
• Tree Depth
• Terminal Branches
• Partial Order
• Hybrid Algorithm
• Minimum Height
• Vertex Degree
• Joining Tree
• Original Graph
• Planar Graphs
• Minimal Representation
• Balanced Tree
• Arbitrary Graph
• Perfect Order