Sparse Matrix Ordering Methods for Interior Point Linear Programming
Edward E. Rothberg, Bruce Hendrickson · INFORMS journal on computing · 1998
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.
Cited by 23 works. doi:10.1287/ijoc.10.1.107
Authors
References
- An Efficient Heuristic Procedure for Partitioning Graphs
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- Computer Solution of Large Sparse Positive Definite Systems.
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- The Elimination form of the Inverse and its Application to Linear Programming
- Computer Solution of Large Sparse Positive Definite
- A multilevel algorithm for partitioning graphs
- Computational experience with a primal-dual interior point method for linear programming
- The Chaco user`s guide. Version 1.0
- Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art