Tokyo Tech News

Parallel Computing for Large-scale Semidefinite Programs


February 28, 2013

SemiDefinite Programs (SDP) are an extension of Linear Programs to the Hilbert space, and serve as a fundamental optimization tools for many practical applications ranging from combinatorial optimizations to quantum chemistry, and sensor network localization problems.

However, recent applications such as sensor network localization problems generate SDPs having extremely sparse Schur complement matrices. Now, instead of straightforward parallel implementation, Makoto Yamashita and colleagues at Tokyo Institute of Technology, Chuo University, and RIKEN have implemented a new parallel scheme to evaluate the sparse Schur matrix in a short time.

First, the computation cost of each element of the Schur complement matrix is estimated based on input data. Then, the elements are distributed to the multiple computation servers so that the loads on all the servers are alike. This parallel scheme is further enhanced with multi-threading computation on each server.

By combining the straightforward implementation and this new parallel scheme, large-scale SDPs with sparse Schur matrices can be handled adequately and solved in a shorter time than before.

Solving large-scale SDPs faster would extend the applicable size in quantum chemistry and sensor network localization problems, and it would provide acceleration in a wide range of numerical optimization.

Authors: Makoto Yamashita1, Katsuki Fujisawa2, Mituhiro Fukuda1, Kazuhide Nakata3, Maho Nakata4
Title of original paper: Parallel Solver for Semidefinite Programming Problem having Sparse Schur Complement Matrix
Journal, volume, pages and year: ACM Transactions on Mathematical Software
39 (1), November 2012, Article No. 6
Digital Object Identifier (DOI): 10.1145/2382585.2382591
Affiliations: 1Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2 Department of Industrial and Systems Engineering, Chuo University, 3 Department of Industrial Engineering and Management, Tokyo Institute of Technology, 4 RIKEN



An approximate solution based on SDP for sensor network localization problems.