The ``inexact'' minimum local fill-in ordering algorithm

Csaba Meszaros

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.