A practical algorithm for making filled graphs minimal

For an arbitrary filled graph G(+) of a given original graph G, we consider the problem of removing fill edges from G(+) in order to obtain a graph M that is both a minimal filled graph of G and a subgraph of G(+). For G(+) with f fill edges and e original edges, we give a simple O(f(e + f)) algorithm which solves the problem and computes a corresponding minimal elimination ordering of G. We report on experiments with an implementation of our algorithm, where we test graphs G corresponding to some real sparse matrix applications and apply well-known and widely used ordering heuristics to find G(+). Our findings show the amount of fill that is commonly removed by a minimalization for each of these heuristics, and also indicate that the runtime of our algorithm on these practical graphs is better than the presented worst-case bound. (C) 2001 Elsevier Science B.V. All rights reserved.