I am currently trying to understand the mesh partitioning using coordinate bisection method. The general idea is clear: Looking at the coordinates (either X or Y or Z direction) and splitting the entities so that in best case both domains contain the same amount of entities.
Now some questions arise for me.
Q1: Is there an algorithm to get the bisection or "cut" or is it more an iterative procedure? I assume that the cuts are made along the global coordinate directions.
Q2: In finite element simulations I want a complete element to be in one of the domains. Thus I have cut exaclty along the nodes and element edges/faces. Can I still use node coordinates for splitting or do I have to use something similar?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ You want to take a look at the literature on mesh partitioning, which is basically an application of "graph partitioning" when you consider the graph in which each node corresponds to one mesh element, and each edge corresponds to whether two elements are neighboring. $\endgroup$– Wolfgang BangerthCommented Aug 15, 2022 at 20:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can definitely use coordinate information to inform mesh partitioning, a brief sketch follows.
Given some set of elements, you can form a point cloud of their centroids and then apply principal component analysis (eigendecomposition of their covariance matrix) to determine the "longest" axis of the cloud. This direction is a good choice for the surface normal of a partitioning plane, because it's likely to have a small edge cut (ie small minimum separator for direct methods, small communication volume for parallel methods, etc). The offset of the partitioning plane could be picked quickly by projecting the centroid of the point cloud onto the cutting direction, or you could perform a bisection-like search over the extents of the cloud and maybe find something a little better.
Once you've picked the plane, classify the elements as above it or below it, and then recurse on the two subsets. Ultimately you'll reach some terminating condition, ie the set is small enough that no further partitioning is needed. Once finished, you can either keep the hierarchical/tree representation of this splitting process, or just collect the sets from the leaves to get a "flattened" representation. (ie splitting 5 levels would give you 2^5=32 parts).
The commenter is correct to point out that you can also submit the graph of the mesh to a graph partitioner (METIS, for instance, there's certainly others), which might be less fuss overall. There is some interesting convergence of ideas here, in that some "spectral clustering" based partitioners ultimately end up synthesizing a coordinate embedding for the graph, and then splitting it along the longest axis (the "Fiedler vector" is good search term to dig up more about these ideas).
