Minimal orderings revisited. (English) Zbl 1044.65035

A new algorithm is derived for computing better minimal orderings and which is more efficient than the algorithm of D. J. Rose, R. E. Tarjan and G. S. Lueker [SIAM J. Comput. 5, 266-283 (1976; Zbl 0353.65019)], while computing minimum ordering is NP-complete. The algorithm begins with any initial ordering and then refines it until a minimal ordering is obtained by generating a sequence of reorderings, each removing additional fill from the current fill graph until a minimal chordal supergraph is obtained. Concepts and structures from sparse Choleski factorization have been used, including elimination trees, supernodes, supernodal elimination trees topological orderings, minimum degree algorithm and column counts. Experimental results are presented for several initial orderings and the algorithm is most efficient when the initial ordering is close to minimal.


65F30 Other matrix algorithms (MSC2010)
65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices


Zbl 0353.65019
Full Text: DOI