Parallel Implementation of Primal-dual Interior-point Methods for Semidefinite Programs

Masakazu Kojima, Katsuki Fujisawa and Makoto Yamashtia
Tokyo Institute of  Technology, Tokyo, Japan

Semidefinite programs arising from many fields such as combinatorial optimization and quantum chemistry become too large to solve on a single processor. They require not only enormous computational time but also huge memory. In this talk, we present the SDPARA (SemiDefinite Programming Algorithm paRAllel version), a parallel version of the SDPA on multiple processors and distributed memory. The main feature of the SDPARA is a parallel computation of the so-called Schur complement matrix and its parallel Cholesky factorization using MPI and ScaLAPACK. We show a high scalability of the SDPARA through numerical results for large scale semidefinite programs on a PC cluster consisting of 64 processor.