pPCx

pPCx: parallel software for linear programming. pPCx stands for ”parallel predictor corrector” package and is a parallel version of the PCx code for Linear Programming developed at the Optimization Technology Center at Argonne National Labs. This is work in progress, people involved from the Cornell side are Thomas Coleman, Chunguang Sun and Michael Wagner, and Steve Wright from Argonne. The basic framework for pPCx is Mehrotra’s predictor corrector interior point method for linear programming. Most of the work in an interior point method lies in solving a symmetric sparse positive (semi-) definite system of linear equations: we’ve successfully hooked up Psspd developed by Chunguang Sun as well as PWSSMP from IBM, both parallel sparse Cholesky solvers that efficiently handle near-degeneracies. We also take care of dense rows and columns efficiently so that we can exploit sparsity in the normal equations as much as possible. The factored matrix is stored in a distributed form, thus enabling the solution of very large problems that cannot be solved on a single processor. The code is written entirely in C (with MPI extensions) and will thus be easily portable to other architectures. The testing is being done in the ACRI on the IBM SP2 at the Cornell Theory Center