  


Parallel solver for semidefinite programming problem having sparse Schur complement matrix
Makoto Yamashita(Makoto.Yamashitais.titech.ac.jp) Abstract: 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 largescale 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 largescale 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 formulacostbased 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 multithreading. In fact, SDPARA is implemented in order to explore parallelism in two fronts: MPIbased and multithreading of CPU cores. The new SDPARA attains a good scalability in general, and found solutions of extremely largescale SDPs arising from POPs which other solvers could not obtain before. Keywords: SemiDefinite Programming, Parallel Computing, PrimalDual InteriorPoint Methods Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Research Report B463, Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology, OhOkayama, Meguro, Tokyo 1528552, September 2010. Download: [PDF] Entry Submitted: 09/14/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  