Comparing dierent graph models for partitioning tetrahedral grids on distributed-memory computers

At RWTH Aachen University the finite element solver DROPS is being developed within the SFB 540 “Model-based experimental analysis of kinetic phenomena in fluid multi-phase reactive systems.” This parallel software package is designed to simulate two-phase flow problems arising from studying the behavior of droplets or falling films with a free surface. Typically, the analysis of such three-dimensional phenomena that are close to reality involves a high demand of both memory resources and computing time. To cope with these problems, we pursue two strategies: adaptive mesh-refinement and parallel computing. First, the refinement algorithm aims for locally refining the tetrahedral mesh in domains of interest. The output of this algorithm is a hierarchy of tetrahedral grids representing the computational domain. While evolving in time during the course of the simulation, the domains of interest may change, and thus, the hierarchy of tetrahedral grids may change as well. Second, the tetrahedra of the finest grid are distributed among several processes. In this domain decomposition setting, each process is responsible for a subdomain, which is represented by a subset of tetrahedra. Finding an appropriate distribution of the tetrahedra among the processes is generally done by graph partitioning techniques that decompose a graph into “equally-sized” subgraphs while minimizing edges connecting vertices in different subgraphs.