A high-performance software package for semidefinite programs: SDPA 7

Makoto Yamashita(Makoto.Yamashitais.titech.ac.jp)
Katsuki Fujisawa(fujisawaindsys.chuo-u.ac.jp)
Kazuhide Nakata(nakata.k.acm.titech.ac.jp)
Maho Nakata(mahoriken.jp)
Mituhiro Fukuda(mituhirois.titech.ac.jp)
Kazuhiro Kobayashi(kobayashinmri.go.jp)
Kazushige Goto(kgototacc.utexas.edu)

Abstract: The SDPA (SemiDefinite Programming Algorithm) Project launched in 1995 has been known to provide high-performance packages for solving large-scale Semidefinite Programs (SDPs). SDPA Ver. 6 solves efficiently large-scale dense SDPs, however, it required much computation time compared with other software packages, especially when the Schur complement matrix is sparse. SDPA Ver. 7 is now completely revised from SDPA Ver. 6 specially in the following three implementation; (i) modification of the storage of variables and memory access to handle variable matrices composed of a large number of sub-matrices, (ii) fast sparse Cholesky factorization for SDPs having a sparse Schur complement matrix, and (iii) parallel implementation on a multi-core processor with sophisticated techniques to reduce thread conflicts. As a consequence, SDPA Ver. 7 can efficiently solve SDPs arising from various fields with shorter time and less memory than Ver. 6 and other software packages. In addition, with the help of multiple precision libraries, SDPA-GMP, -QD and -DD are implemented based on SDPA to execute the primal-dual interior-point method with very accurate and stable computations. The objective of this paper is to present brief explanations of SDPA Ver. 7 and to report its high performance for large-scale dense and sparse SDPs through numerical experiments compared with some other major software packages for general SDPs. Numerical experiments also show the astonishing numerical accuracy of SDPA-GMP, -QD and -DD.

Keywords: semidefinite program, primal-dual interior-point method, high-accuracy calculation

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation:

Download: [PDF]

Entry Submitted: 01/28/2010
Entry Accepted: 01/28/2010
Entry Last Modified: 01/28/2010

Modify/Update this entry