Optimization Online


Parallel Computing on Semidefinite Programs

Steven Benson (benson***at***mcs.anl.gov)

Abstract: This paper demonstrates how interior-point methods can use multiple processors efficiently to solve large semidefinite programs that arise in VLSI design, control theory, and graph coloring. Previous implementations of these methods have been restricted to a single processor. By computing and solving the Schur complement matrix in parallel, multiple processors enable the faster solution of medium and large problems. The dual-scaling algorithm for semidefinite programming was adapted to a distributed-memory environment and used to solve medium and large problems than faster than could previously be solved by interior-point algorithms. Three criteria that influence the parallel scalability of the solver are identified. Numerical results show that on problems of appropriate size and structure, the implementation of an interior-point method exhibits good scalability on parallel architectures.

Keywords: Semidefinite programming, numerical optimization, parallel computing, high-performance computing

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

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: Preprint ANL/MCS-P939-0302; Mathematics and Computer Science Division Argonne National Laboratory 9700 S. Cass Avenue Argonne, IL, 60439; March 2002

Download: [Postscript][PDF]

Entry Submitted: 03/26/2002
Entry Accepted: 03/26/2002
Entry Last Modified: 04/22/2003

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