  


A Parallel PrimalDual InteriorPoint Method for Semidefinite Programs Using Positive Definite Matrix Completion
Kazuhide Nakata (knakatame.titech.ac.jp) Abstract: A parallel computational method SDPARAC is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPAC proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of its coefficient matrix. SDPARA can effectively solve SDPs with a large number of equality constraints, however, it does not solve SDPs with a large scale matrix variable with similar effectiveness. SDPAC is a primaldual interiorpoint method using the positive definite matrix completion technique by Fukuda et al, and it performs effectively with SDPs with a large scale matrix variable, but not with a large number of equality constraints. SDPARAC benefits from the strong performance of each of the two methods. Furthermore, SDPARAC is designed to attain a high scalability by considering most of the expensive computations involved in the primaldual interiorpoint method. Numerical experiments with the three parallel software packages SDPARAC, SDPARA and PDSDP by Benson show that SDPARAC efficiently solve SDPs with a large scale matrix variable as well as a large number of equality constraints with a small amount of memory. Keywords: Semidefinite Program, PrimalDual InteriorPoint Method, Parallel Computation, Positive Definite Matrix Completion, Numerical Experiment, PC Cluster Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Optimization Software and Modeling Systems (Parallel Algorithms ) Category 3: Combinatorial Optimization (Graphs and Matroids ) Citation: Research Report B398, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Meguro, Tokyo 1528552. November 2003. Download: [Postscript][Compressed Postscript][PDF] Entry Submitted: 11/17/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  