A parallel formulation of interior point algorithms

Abstract

In this paper we describe a scalable parallel formulation of interior point algorithms. Through our implementation on a 256-processor nCUBE 2 parallel computer, we show that our parallel formulation utilizes hundreds of processors efficiently and delivers much higher performance and speedups than reported earlier. These speedups are a result of our highly efficient parallel algorithm for solving a linear symmetric positive definite system using Cholesky factorization. We also evaluate a number of ordering algorithms for sparse matrix factorization in terms of their suitability for parallel Cholesky factorization.