We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the {\em matrix completion} scheme of Fukuda et al. \cite{fukuda_et_al} to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase 2, we solve the resulting block-angular SDP using a {\em regularized interior point decomposition} algorithm, in an iterative fashion between a master problem (a quadratic program); and decomposed and distributed subproblems (smaller SDPs) in a parallel and distributed high performance computing environment. We compare our MPI implementation of the decomposition algorithm on the distributed {\em Henry2} cluster with the OpenMP version of CSDP \cite{borchers_young} on the IBM Power5 shared memory system at NC State University. Our computational results indicate that the decomposition algorithm a) solves large SDPs to 2-3 digits of accuracy where CSDP runs out of memory; b) returns competitive solution times with the OpenMP version of CSDP, and c) attains a good parallel scalability. Comparing our results with Fujisawa et al. \cite{fujisawa_et_al}, we also show that a suitable modification of the matrix completion scheme can be used in the solution of larger SDPs than was previously possible.

## Citation

Technical Report, Department of Mathematics, North Carolina State University, Raleigh, NC, 27695, April 2008. Accepted for publication in "Computational Optimization and Applications". Also available at http://www4.ncsu.edu/~kksivara/publications/parallel-conic-blockangular.pdf

## Article

View A PARALLEL interior point decomposition algorithm for block-angular semidefinite programs