Using a massively parallel processor to solve large sparse linear programs by an interior-point method

Joseph Czyzyk*, Robert H Fourer, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)553-565
Number of pages13
JournalSIAM Journal of Scientific Computing
Volume19
Issue number2
DOIs
StatePublished - Jan 1 1998

Keywords

  • Interior-point methods
  • Large-scale optimization
  • Linear programming
  • Parallel computation

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Using a massively parallel processor to solve large sparse linear programs by an interior-point method'. Together they form a unique fingerprint.

Cite this