Optimization Online


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

Makoto Yamashita(Makoto.Yamashita***at***is.titech.ac.jp)
Katsuki Fujisawa(fujisawa***at***indsys.chuo-u.ac.jp)
Kazuhide Nakata(nakata.k.ac***at***m.titech.ac.jp)
Maho Nakata(maho***at***riken.jp)
Mituhiro Fukuda(mituhiro***at***is.titech.ac.jp)
Kazuhiro Kobayashi(kobayashi***at***nmri.go.jp)
Kazushige Goto(kgoto***at***tacc.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 )


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society