A parallel formulation of interior point algorithms

George Karypis, Anshul Gupta, and Vipin Kumar
Supercomputing, pp. 204-213, 1994
Download Paper
In recent years, interior point algorithms have been used successfully for solving medium-
to large-size linear programming (LP) problems. In this paper we describe a highly
parallel formulation of the interior point algorithm.
A key component of the interior point algorithm is the solution of
a sparse system of linear equations using Cholesky
factorization. The performance of parallel Cholesky factorization is determined by
(a) the communication overhead incurred by the algorithm, and (b) the load imbalance
among the processors.
In our parallel interior point algorithm, we use our recently developed
parallel multifrontal algorithm that has the smallest communication
overhead over all parallel algorithms for Cholesky factorization developed to date.
The computation imbalance depends on the shape of the elimination tree associated
with the sparse system reordered for factorization.
To balance the computation, we implemented and evaluated four different ordering algorithms.
Among these algorithms, Kernighan-Lin and spectral nested dissection
yield the most balanced elimination trees and greatly increase the amount of parallelism
that can be exploited.
Our preliminary implementation achieves a speedup as high as 108 on 256-processor
nCUBE~2 on moderate-size problems.
Research topics: Parallel processing | Scientific computing