Min-max-boundary domain decomposition

Domain decomposition is one of the most effective and popular parallel comp uting techniques for solving large-scale numerical systems. In the special case when the amount of computation in a subdomain is proportional to the v olume of the subdomain, domain decomposition amounts to minimizing the surf ace area of each subdomain while dividing the volume evenly. Motivated by t his fact, we study the following,min-max-boundary multi-way partitioning pr oblem. Given a graph G and an integer k > 1, we would like to divide G into k subgraphs G(1),...,G(k) (by removing edges) such that (i) \G(i)\ = Theta (\G \ /k) for all i is an element of {1,...,k}; and (ii) the maximum bounda ry size of any subgraph (the set of edges connecting it with other subgraph s) is minimized. We provide an algorithm that given G, a well-shaped mesh i n d dimensions, finds a partition of G into k subgraphs G(1),...,G(k), such that for all i, G(i), has Theta(\G \ /k) vertices and the number of edges connecting Ci with the other subgraphs is O((\G \ /k)(1-1/d)). Our algorith m can find such a partition in O(\G \ logk) time. Finally, we extend our re sults to vertex-weighted and vertex-based graph decomposition. Our results can be used to simultaneously balance the computational and memory loads on a distributed-memory parallel computer without incurring large communicati on overhead. (C) 2001 Elsevier Science B.V. All rights reserved.