ncku-talk2011-04-15

NCTS(South)/ NCKU Math Colloquium

DATE 2011-04-15　09:00-11:00

PLACE R204, 2F, NCTS, NCKU

SPEAKER Professor Makoto Yamashita（Tokyo Institute of Technology）

TITLE Part 2. SDPA : High performance package for SemiDefinite Programs

ABSTRACT SDP (SemiDefinite Programming) is an extension of Linear Programming to the space of symmetric matrices. The range of its applications is very wide and includes control theory, combinatorial optimization, quantum chemistry and financial engineering. Hence, solving large-scale SDPs has a great importance to these fields. Our software package SDPA is designed to solve large-scale SDPs in a short time.
The base of SDPA is Primal-Dual Interior-Point Method, a polynomial-time algorithm. We combine various techniques to realize speedup in SDPA, e.g., exploiting sparsity, sparse Cholesky factorization, multiple threading. We also implement some variants of SDPA. With the help of parallel computing, SDPARA (a parallel version of SDPA) can solve extremely large-scale SDPs. SDPA-GMP can obtain ultra high accurate solution, by replacing usual double precision with GMP (GNU multiple precision) library. In this talk, we will start from a fundamental framework of Primal-Dual Interior-Point method. Then we will explain the techniques embedded in each software and how much the techniques contribute to reduce the computation time.

NCTS(South)/ NCKU Math Colloquium

DATE	2011-04-15　09:00-11:00

PLACE	R204, 2F, NCTS, NCKU

SPEAKER	Professor Makoto Yamashita（Tokyo Institute of Technology）

TITLE	Part 2. SDPA : High performance package for SemiDefinite Programs

ABSTRACT	SDP (SemiDefinite Programming) is an extension of Linear Programming to the space of symmetric matrices. The range of its applications is very wide and includes control theory, combinatorial optimization, quantum chemistry and financial engineering. Hence, solving large-scale SDPs has a great importance to these fields. Our software package SDPA is designed to solve large-scale SDPs in a short time. The base of SDPA is Primal-Dual Interior-Point Method, a polynomial-time algorithm. We combine various techniques to realize speedup in SDPA, e.g., exploiting sparsity, sparse Cholesky factorization, multiple threading. We also implement some variants of SDPA. With the help of parallel computing, SDPARA (a parallel version of SDPA) can solve extremely large-scale SDPs. SDPA-GMP can obtain ultra high accurate solution, by replacing usual double precision with GMP (GNU multiple precision) library. In this talk, we will start from a fundamental framework of Primal-Dual Interior-Point method. Then we will explain the techniques embedded in each software and how much the techniques contribute to reduce the computation time.