Using a Massively Parallel Processor to Solve Large Sparse Linear Programs by an Interior-Point Method
Authors:
- Joseph CzyzykJCJoseph Czyzyk
- Robert FourerRFRobert Fourer
- Sanjay MehrotraSMSanjay Mehrotra
- 1 January 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 19 (2) , 553-565
Abstract
Most implementations of interior-point methods for linear programming rely on some form of elimination to solve the key equation system or systems at each iteration. Although these systems are typically very sparse, a substantial dense block often arises as the elimination proceeds. We describe a strategy that uses a serial "front-end" computer to carry out the sparse part of the elimination and a massively parallel processor to complete the elimination on the dense block. Through computational tests, we show that two such computers working together can solve hard linear programs much faster than either could alone. We conclude that our strategy is technically feasible now but that its components will have to be closer to the state of the art---in both serial and parallel processing---for it to be feasible in an economic sense.Keywords
This publication has 9 references indexed in Scilit:
- A Study of the Augmented System and Column-Splitting Approaches for Solving Two-Stage Stochastic Linear Programs by Interior-Point MethodsINFORMS Journal on Computing, 1995
- Solving symmetric indefinite systems in an interior-point method for linear programmingMathematical Programming, 1993
- Symmetric indefinite systems for interior point methodsMathematical Programming, 1993
- On the Implementation of a Primal-Dual Interior Point MethodSIAM Journal on Optimization, 1992
- Highly Parallel Sparse Cholesky FactorizationSIAM Journal on Scientific and Statistical Computing, 1992
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear ProgrammingSIAM Journal on Optimization, 1992
- Computational experience with a primal-dual interior point method for linear programmingLinear Algebra and its Applications, 1991
- Data Structures and Programming Techniques for the Implementation of Karmarkar's AlgorithmINFORMS Journal on Computing, 1989
- An analysis of an available set of linear programming test problemsComputers & Operations Research, 1989