Algorithms for Graph Partitioning and Fill Reducing Ordering for Domain Decomposition Methods ∗

This paper focuses on domain decomposition-based numerical simulations whose subproblems corresponding to the various subdomains are solved using sparse direct factorization methods (e.g., 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 this 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 predictorcorrector 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 considerabl