Abstract:
The main cost of solving a linear programming problem using an interior point method is usually the cost of solving a sparse, symmetric linear system of equations, $A \Theta 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 thus reduce the required work. The paper evaluates several methods for performing fill-reducing orderings 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.