Sparse Matrix Ordering Methods for Interior Point Linear Programming
Edward Rothberg, Bruce Hendrickson
INFORMS Journal on Computing · 1998 · Volume 10 · Issue 1
Abstract
The main cost of solving a linear programming problem using an interior point method is usually the cost of solving a series of sparse, symmetric linear systems of equations, A Θ A T x = b . These systems are typically solved using a sparse direct method. The first step in such a method is a reordering of the rows and columns of the matrix to reduce fill in the factor and/or reduce the required work. This article evaluates several methods for performing fill-reducing ordering on a variety of large-scale linear programming problems. We find that a new method, based on the nested dissection heuristic, provides significantly better orderings than the most commonly used ordering method, minimum degree.
Keywords
linear programming, interior point methods, interior point, sparse matrix
Enable JavaScript for citation tools and additional paper interactions.