SOLVING LARGE SCALE LINEAR PROGRAMMING PROBLEMS USING AN INTERIOR POINT METHOD ON A MASSIVELY PARALLEL SIMD COMPUTER

Abstract

The interior point method (IPM) is now well established as a competitive technique for solving very large scale linear programming problems. The leading variant of the interior point method is the primal dual—predictor corrector algorithm due to Mehrotra. The main computational steps of this algorithm are the repeated calculation and solution of a large sparse positive definite system of equations

We describe an implementation of the predictor corrector IPM algorithm on MasPar, a massively parallel SIMD computer. At the heart of the implementation is a parallel Cholesky factorization algorithm for sparse matrices. Our implementation uses a new scheme of mapping the matrix onto the processor grid of the MasPar, that results in a more efficient Cholesky factorization than previously suggested schemes

The IPM implementation uses the parallel unit of MasPar to speed up the factorization and other computationally intensive parts of the IPM. An important part of this implementation is the judicious division of data and computation between the front-end computer, that runs the main IPM algorithm, and the parallel unit. Performance results on standard industrial test problems are presented and discussed.

KEY WORDS:

• Cholesky factorization
• interior point methods
• linear programming
• parallel computers
• SIMD machines
• sparse matrix factorization

C.R. CATEGORIES:

• G.1.3.

Notes

∗This work was performed while the author was visiting the Department of Mathematics and Statistics, Brunei University.