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

By: Anshul Gupta

Published in: RC20467 in 1996

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

8178.ps.gz

Questions about this service can be mailed to reports@us.ibm.com .