Accession Number : ADA327991

Title :   Parallel Gaussian Elimination with Linear Work and Fill,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Bornstein, Claudson ; Maggs, Bruce ; Miller, Gary ; Ravi, R.

PDF Url : ADA327991

Report Date : MAY 1997

Pagination or Media Count : 33

Abstract : This paper presents an algorithm for finding parallel elimination orderings for Gaussian elimination. Viewing a system of equations as a graphs, 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 long n less height, but with a factor of O(square root of (log n)) more fill.

Descriptors :   *ALGORITHMS, *HEURISTIC METHODS, OPTIMIZATION, MATRICES(MATHEMATICS), GRAPHS, PARALLEL PROCESSING.

Subject Categories : Operations Research
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE