Shape-Optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM

R. Diekmann, R. Preis, F. Schlimbach and C. Walshaw


We present a dynamic distributed load balancing algorithm for parallel, adaptive Finite Element simulations in which we use preconditioned Conjugate Gradient solvers based on domain-decomposition. The load balancing is designed to maintain good partition Aspect Ratio and we show that cut size is not always the appropriate measure in load balancing. Furthermore, we attempt to answer the question why the Aspect Ratio of partitions plays an important role for certain solvers. We define and rate different kinds of Aspect Ratio and present a new center-based partitioning method of calculating the initial distribution which implicitly optimizes this measure. During the adaptive simulation, the load balancer calculates a balancing flow using different versions of the diffusion algorithm and a variant of breadth first search. Elements to be migrated are chosen according to a cost function aiming at the optimization of subdomain shapes. Experimental results for Bramble's preconditioner and comparisons to state-of-the-art load balancers show the benefits of the construction.

Key words. Mesh Partitioning; Loadbalancing; Shape-Optimization; Aspect Ratio; Parallel; Adaptive; Finite-Element-Method

Fri Aug 13 13:42:00 BST 2004