×

Fast computation of minimal fill inside a given elimination ordering. (English) Zbl 1176.65027

Summary: Minimal elimination orderings were introduced by D. J. Rose, R. E. Tarjan and G. S. Lueker [SIAM J. Comput. 5, 266–283 (1976; Zbl 0353.65019)], and during the last decade they have received increasing attention. Such orderings have important applications in several different fields, and they were first studied in connection with minimizing fill in sparse matrix computations. Rather than computing any minimal ordering, which might result in fill that is far from minimum, it is more desirable for practical applications to start from an ordering produced by a fill-reducing heuristic and then compute a minimal fill that is a subset of the fill produced by the given heuristic. This problem has been addressed previously, and there are several algorithms for solving it. The drawback of these algorithms is that either there is no theoretical bound given on their running time, although they might run fast in practice, or they have a good theoretical running time, but they have never been implemented, or they require a large machinery of complicated data structures to achieve the good theoretical time bound.
In this paper, we present an algorithm called MCS-ETree for solving the mentioned problem in \(O(nm A(m,n))\) time, where \(m\) and \(n\) are, respectively, the number of edges and vertices of the graph corresponding to the input sparse matrix and \(A(m,n)\) is the very slowly growing inverse of Ackerman’s function. A primary strength of MCS-ETree is its simplicity and its straightforward implementation details. We present run time test results to show that our algorithm is fast in practice. Thus our algorithm is the first that both has a provably good running time with easy implementation details and is fast in practice.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory

Citations:

Zbl 0353.65019
PDFBibTeX XMLCite
Full Text: DOI