Distributed Genetic Algorithms for Partitioning Uniform Grids

Abstract

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.