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.
Citation
Preprint ANL/MCS-P939-0302; Mathematics and Computer Science Division Argonne National Laboratory 9700 S. Cass Avenue Argonne, IL, 60439; March 2002