SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical programming. SDP provides a practical computation framework for many research fields. Some applications, however, require solving large-scale SDPs whose size exceeds the capacity of a single processor in terms of computational time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel version) developed by Yamashita et al. was designed to solve such large-scale SDPs. Its parallel performance is remarkable for general SDPs in most cases. However, the parallel implementation is less successful in some sparse SDPs from the latest applications such as for Polynomial Optimization Problems (POPs) or Sensor Network Location (SNL) problems, since the previous SDPARA can not directly handle sparse Schur complement matrices (SCMs). In this paper, we focus on the sparsity of the SCM and propose new parallel implementations, the formula-cost-based distribution, and the replacement of the dense Cholesky factorization. Through numerical results, we confirm that these features are keys to solve SDPs having sparse SCMs faster on parallel computer systems, and they are further enhanced by multi-threading. In fact, SDPARA is implemented in order to explore parallelism in two fronts: MPI-based and multi-threading of CPU cores. The new SDPARA attains a good scalability in general, and found solutions of extremely large-scale SDPs arising from POPs which other solvers could not obtain before.
Citation
Research Report B-463, Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, September 2010.
Article
View Parallel solver for semidefinite programming problem having sparse Schur complement matrix