Graph Partitioning for FEM Applications: Reducing the Communication Volume with DSHEM

The finite element method is primarily utilized to numerically solve partial differential equations, most commonly by the use iterative methods, over a compact domain. The PDEs domain is represented by a mesh of information which needs to be distributed among all available processors in a parallel computer. Distributing the mesh, known as the mesh partitioning problem, is NP-complete. Much effort focuses on graph partitioning and parallelization to address it. We introduce a new vertex matching model called Directed Sorted Heavy Edge Matching intended to reduce the communication volume during FEM simulations and ensure efficient execution on distributed systems. Finally, we provide performance analysis of DSHEM and comment on its benefits.