PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 20 February 2004

Modifying a given elimination ordering to reduce fill

Pinar Heggernes and Yngve Villanger
University of Bergen
Norway

Abstract:

When factorizing sparse symmetric positive definite matrices, computing a permutation of the given matrix to minimize the number of added nonzero entries, called fill, is essential. Unfortunately this problem is NP-hard, and therefore various heuristics, like Minimum Degree and Nested Dissection, are widely used to produce good, although not optimal, permutations. Graph theory is a convenient and established tool for sparse matrix computations. For a given symmetric matrix A, its associated graph G=G(A) is simply the graph of which A is an adjacency matrix. Computing a permutation of A is equivalent to computing a vertex ordering of G, called an elimination ordering. Thus, finding a permutation of A to minimize the number of fill entries is equivalent to finding an elimination ordering of G to minimize the number of added fill edges. It is a well known fact that the graph of the Cholesky factor L of A, G(L) is a chordal graph. An elimination ordering (and the resulting fill) is minimal if no fill edges can be removed without destroying chordality. Since computing minimum fill is NP-hard, extensive research has been done on computing minimal fill, and several polynomial time algorithms exist for this. Unfortunately minimal fill can in general be far from minimum. However, elimination orderings that both are minimal and produce low fill are highly desirable for sparse matrix computations. It has been observed in several papers that Minimum Degree quite often produces minimal elimination orderings.

In this paper we show how to modify a given elimination ordering to obtain an ordering that is both minimal and that results in fewer fill edges than the original ordering. Given an elimination ordering alpha and a chosen k, we show how to locally reorder sequences of k consecutive vertices of alpha to achieve fewer fill edges. We say that alpha is k-optimal if no such enhancement is possible. An interesting result that we show is that Minimum Degree is 2-optimal, but not 3-optimal. Thus even Minimum Degree orderings are possible to use as starting elimination orderings to achieve better orderings. Our general algorithm is the following: Start with a given elimination ordering. Make it minimal by removing unnecessary fill edges using one of the existing algorithms for this purpose. Then compute a reordering of it so that the resulting ordering becomes k-optimal. Now the resulting ordering is not necessarily minimal, because making an ordering k-optimal does not only remove edges, it may also add edges. However we know that it has fewer fill edges than the original ordering. Then we continue with a second iteration, making the last ordering minimal by removing edges, and reordering to make it k-optimal. We run new iterations as long as we achieve better orderings. We stop iterating when the resulting k-optimal ordering is also minimal and thus no fill edges can be removed further. For fast implementation and high quality orderings it is important to choose a good k. We show with practical tests that fill can be reduced considerably from the given ordering, even when the given ordering is a good ordering, like a Minimum Degree ordering. We observe that the process stops after a few iterations. We experiment with different k values to balance between running time and good orderings.

Home page