%A Ioannis T. Christou
%T Distributed Genetic Algorithms for Partitioning Uniform Grids
%D October 1996
%R 96-09
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X In this thesis the author presents a new method for partitioning general
large uniform 5-point grids into sub-domains of given areas having minimum
total perimeter. For applications in scientific computing in parallel
environments, this problem corresponds to minimizing the communication
overhead between processors while observing load balancing constraints
dictated by the speed of each individual processor. For a large class
of grid shapes it is shown that the partition produced by this method
is asymptotically optimal as the problem parameters grow to infinity. A
new distributed Genetic Algorithm based on this decomposition theory
significantly outperforms other well-known methods such as the spectral
bisection (or quadrisection) methods and the geometric mesh partitioner.