pPCx: Parallel Software for Linear Programming

Thomas F. Coleman, Joseph Czyzyk, Chunguang Sun, Michael Wagner, Stephen J. Wright

We present a parallel implementation of a primal-dual infeasible interior point method for linear programming. The underlying algorithm is based on Mehrotra's predictor-corrector idea, a serial implementation was released at Argonne National Lab as PCx. Most of the work in an interior point method lies in solving a symmetric sparse positive (semi-)definite system of linear equations: we present a new parallel multifrontal Cholesky factorization that efficiently handles dense rows and columns as well as near-degeneracies. We discuss implementation details and report performance results obtained at the Cornell Theory Center on an IBM SP2.

CCOP TR 96-14, Cornell University, Ithaca, NY 14853, 12/96

Contact: mwagner@cs.cornell.edu