Multi-Coordination Mehtods for Parallel Solution of Block-Angular Programs

Abstract

This thesis is concerned with the parallel solution of smooth block-angular programs using multiple coordinators. The research herein extends the three phase method of Schultz and Meyer, who use barrier decomposition methods with complex coordinators which are less suited to parallel computation. We start by surveying the existing literature for block-angular programs and reviewing barrier function methods and the Schultz-Meyer method. We then present our synchronous multi-coordination schemes and prove their convergence. We tested our algorithms on the Patient Distribution System problems, a class of large-scale real world multicommodity network flow problems. Computational results on the CM-5 parallel supercomputer demonstrated that the method was significantly faster than in Schultz-Meyer predecessor. We also present multiple coordinator asynchronous schemes to solve block-angular programs and prove the convergence of those methods.