%A Michael C. Ferris
%A Jeffrey D. Horn
%T Partitioning Mathematical Programs for Parallel Solution
%D May 1994
%R TR 1232
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X This paper describes heuristics for partitioning a general M x N
matrix into doubly-bordered, block-diagonal form. Such heuristics are
useful for decomposing large, constrained, optimization problems into
forms that are amenable to parallel processing. The heuristics
presented are all O((M+N)^2 log(M+N)) and are easily implemented. The
application of such techniques for solving large linear programs is
described. Extensive computational results on the effectiveness of
our partitioning procedures and their usefulness for parallel
optimization are presented.