## Sparse Matrix Ordering Methods for Interior Point Linear Programming

### Edward Rothberg and Bruce Hendrickson

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\Theta A^Tx=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. This paper 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.

Manuscript, January 1996.