Partitioning Algorithms for Simultaneously Balancing Iterative and Direct Methods

Abstract

This paper focuses on domain decomposition-based numerical simulations whose sub-problems corresponding to the various subdomains are solved using sparse direct factorization methods (eg., FETI). Effective load-balancing of such computations requires that the resulting partitioning simultaneously balances the amount of time required to factor the local subproblem using direct factorization, and the number of elements assigned to each processor. Unfortunately, existing graph-partitioning algorithms cannot be used to load-balance these type of computations as they can only compute partitionings that simultaneously balance numerous constraints defined a~priori on the vertices and optimize different objectives defined locally on the edges. To address this problem, we developed an algorithm that follows a {em predictor-corrector} approach that first computes a high-quality partitioning of the underlying graph, and then modifies it to achieve the desired balancing constraints. During the corrector step we compute a fill reducing ordering for each partition, and then we modify the initial partitioning and ordering so that our objectives are satisfied. Experimental results show that the proposed algorithm is able to reduce the fill-in of the overweight sub-domains and achieve a considerably better balance.