Graph Partitioning Based Sparse Matrix Orderings for Interior-Point Algorithms

Anshul Gupta

The key computational step in interior-point (IP) methods for solving linear programming (LP) problems is the solution of a sparse symmetric system of linear equations. The time and the memory requirements of this step depend on the initial ordering of rows and columns in the symmetric coefficient matrix. Computing an optimal ordering for sparse matrix factorization is an NP-complete problem and developing fast and effective ordering heuristics has been a subject of research for almost three decades. Currently, a heuristic known as Multiple Minimum Degree (MMD)} (or one of its variants) is almost universally employed by the LP community while using IP methods. In this paper, we show that a completely different approach to sparse matrix ordering that is based on graph partitioning is significantly more suitable for the matrices arising in an IP computation than MMD or its variants. Experiments with our ordering algorithm show a cumulative speedup by a factor of 2.2 and an average speedup of 1.45 over a minimum-degree based ordering for solving a comprehensive suite of real optimization problems. In addition, our graph-partitioning based ordering algorithm is more parallelizable than minimum-degree based orderings algorithm and it renders the ordered matrix more amenable to parallel factorization.

IBM Research Report RC 20467,  May 21 1996, 
IBM T. J. Watson Research Center
P. O. Box 218
Yorktown Heights, NY 10598