An algorithm for domain partitioning with load balancing

Abstract

An algorithm for domain partitioning with iterative load balancing is presented. A recursive graph labeling scheme is used to distribute elements among subdomains at each iteration. Both graph distance information and information about neighbor vertices are employed during the labeling process. Element quantities for balanced subdomains are predicted, solving the algebraic load balancing problem after each iteration. The same graph labeling scheme with slight modifications is applied to node renumbering inside subdomains. The proposed algorithm is especially suitable for load balancing when a direct method is used for subdomain condensation and the evaluation of cost function is time consuming. Several examples of optimized partitioning of irregular and regular meshes show that load balancing can be achieved with one to three iterations.

Citation

Nikishkov, G.P., Makinouchi, A., Yagawa, G. and Yoshimura, S. (1999), "An algorithm for domain partitioning with load balancing", Engineering Computations, Vol. 16 No. 1, pp. 120-135. https://doi.org/10.1108/02644409910251300