%A Golbon Zakeri
%T MULTI-COORDINATION METHODS FOR PARALLEL SOLUTION OF BLOCK-ANGULAR PROGRAMS
%D May 1995
%R 95-08
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X 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 convergence of those methods.