Sparse matrix ordering methods for interior point linear programming

Sparse matrix ordering methods for interior point linear programming

0.00 Avg rating0 Votes
Article ID: iaor1999410
Country: United States
Volume: 10
Issue: 1
Start Page Number: 107
End Page Number: 113
Publication Date: Dec 1998
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: interior point methods
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ΘATx = 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.

Reviews

Required fields are marked *. Your email address will not be published.