Multi-coordination methods for parallel solution of block-angular programs
Golbon Zakeri · 1996
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, as well as on some randomly generated multicommodity network flow problems. Computational results on the CM-5 parallel supercomputer demonstrated that the method was significantly faster than its Schultz-Meyer predecessor. We also present multiple coordinator asynchronous schemes to solve block-angular programs and prove the con...