The ``inexact'' minimum local fill-in ordering algorithm
In the paper we discuss an ordering algorithm for interior point methods
of large sparse linear programming problems. Our method is based on the
minimum local fill-in heuristic, but includes some assumptions of the
minimum degree ordering. The new method considerably outperforms in speed
the minimum local fill-in and generally results in sparser factorization
than minimum degree. We discuss implementation details and programming
techniques, and compare our method on a wide variety of linear programming
test problems with the Sparspak's GENQMD subroutine which was for a long
time public accesible from Netlib.
Working Paper WP 95-7, Computer and Automation Institute,
Hungarian Academy of Sciences, Budapest.