Load balancing for the parallel adaptive solution of partial differential equations (Q1344328)

The authors are concerned with a problem that arises when one wishes to exploit the advantages both of parallel computation and of adaptive finite element strategies. The problem is that adaptivity leads to a restructuring of the finite element mesh, with a consequent redistribution of processor loading. This can lead to processor load imbalances which militate against an efficient solution procedure. The authors discount recursive bisection methods as a procedure for partitioning the domain into subdomains with balanced loading, due to the expense that would be entailed in using this approach in conjunction with an adaptive method. Instead, they propose three strategies for resolving the problem. The first, tiling, is based on a dynamic load balancing technique due to \textit{E. Leiss} and \textit{H. N. Reddy} [Distributed load balancing: design and performance analysis. W. M. Keck Research Computation Laboratory 5, 205-270 (1989)]. It is applicable to two-dimensional structured meshes. For unstructured meshes or for three-dimensional problems it is not a feasible method since it can be expensive. Thus an alternative procedure, redistribution through pairwise exchanges, is introduced to deal with such problems. It builds on tiling, but exploits graph theoretical ideas systematically and effectively. The last alternative is octree decomposition, which is also suitable for three-dimensional unstructured meshes, and which exploits the properties of the underlying tree structure. The three methods proposed in this paper are all tested on a wide range of examples, which illustrate very clearly their performance in practice.