Mesh partitioning is the first step in enabling parallel computation for solving PDEs. For an unstructured computational mesh, the task of partitioning is nontrivial, which can be formulated as an optimization problem with two goals. The first goal is load balancing, i.e., dividing the computational work evenly among the subdomains. The second goal is communication overhead minimization, i.e., limiting the subsequent inter-subdomain communication. Traditionally, an unstructured mesh is translated to a graph before partitioning, where the graph's nodes correspond to the mesh entities and the edges reflect the direct couplings between mesh entities.

In the presence of strong coefficient heterogeneity in a PDE, the coupling between the degrees of freedom (e.g., the nonzero values in a linear system arisen from the discretization) will also exhibit strong heterogeneity. It is numerically beneficial to group the degrees of freedom that have strong in-between couplings in the same subdomain, whereas the weaker couplings are prioritized as places for the separation cuts between subdomains. This is achieved by heterogeneously weighting the edges of the graph, which is then partitioned by a graph partitioning algorithm that almost exclusively aims to minimize the so-called edge cut (sum of weights of all the cut-through edges).

Such an approach requires care, because an over-weighting of edges that represent strong couplings may result in too few ``light-weight'' edges that can be candidates for cut between subdomains. This may again lead to bad partitioning results where e.g., a subdomain consists of several disjoint patches. An accompanying weakness is that the associated edge-cut value no longer bears resemblance to the true communication overhead that will arise in the parallel solution process of the PDE.

This talk will report the results of ongoing work on investigating the weaknesses of the edge-cut-oriented graph partitoning strategy in the presence of strong coefficient heterogeneity. We will use concrete examples from reservoir simulations that involve strong disparity in key geological coefficients. Moreover, we aim to experiment with possible improvements to the current graph partitioning paradigm by giving less emphasis to edge cut while incorporating a new metric that better resembles the overhead of inter-subdomain communication.