Load Balancing for Problems with Good Bisectors, and Applications in Finite Element Simulations

This paper studies load balancing issues for classes of problems with certain bisection properties. A class of problems has ff-bisectors if every problem in the class can be subdivided into two subproblems whose weight (i.e. workload) is not smaller than an ff-fraction of the original problem. It is shown that the maximum weight of a subproblem produced by Algorithm HF, which partitions a given problem into N subproblems by always subdividing the problem with maximum weight, is at most a factor of b1=ffc \Delta (1 \Gamma ff) greater than the theoretical optimum (uniform partition). This bound is proved to be asymptotically tight. Two strategies to use Algorithm HF for load balancing distributed hierarchical finite element simulations are presented. For this purpose, a certain class of weighted binary trees representing the load of such applications is shown to have 1=4-bisectors. The maximum resulting load is at most a factor of 9=4 larger than in a perfectly uniform distribution in this case