Graph Partitioning Based Sparse Matrix Orderings for Interior-Point Algorithms

Keywords: Linear Programming, Interior-Point Methods, Sparse Matrices, Ordering, Graph Partitioning, Sparse Linear Systems. 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 $(AD^2A^T)\Delta y = b$. The time and the memory requirements of this step depend on the initial ordering of rows and columns in the symmetric matrix $AD^2A^T$. 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 {\em 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 itsshow 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. variants. Experiments with our ordering algorithm