Tech Report CS-91-19

Approximating Fill in Solving Sparse Linear Systems

Ajit Agrawal, Philip Klein and R. Ravi

March 1991


In this paper, we present the first approximation algorithm for minimizing fill in solving a symmetric positive-definite sparse linear system of equations. Moreover, the elimination ordering of variables output by the algorithm also approximately minimizes two other important quantities: the total number of multiplications and the total time taken on a parallel machine to solve the problem using gaussian elimination. For a constant number of nonzero elements in each row and column, the performance guarantee is polylogarithmic in the number of variables. The bound is weaker in other cases.

The problem of minimizing fill is directly related to the problem of minimum graph chordalization for which we give an approximation algorithm here. The algorithm is based on a method of Leighton and Rao for finding approximate balanced node separators in undirected graphs.

(complete text in pdf)