# Mesh partition quality

I am working on static FE mesh partitioning and in order to achieve a good quality partitioning I want to know how to drecrease interprocessor communication by increasing the connectivity of elements in a subdomain.For a 2D mesh we have edge connectivity and vertex conectivity.As the names suggest 2 regions are edge-connected if they share a common egde(2 elements share a common egde) and vertex-connected if they share a common vertex(2 elements share a common node).Edge-connectivity for a 2D mesh is more desirable since if elements in a subdomain share an edge they also share vertices which leads to less communication.I used METIS for a good quality partitioning but I noticed sometimes it creates subdomains with elements that may share a node and not an edge.Any ideas or suggestions on how to avoid this would be important.

## 1 Answer

In principle, you could try to quantify how much communication two cells $$K_i$$ and $$K_j$$ will have to exchange if (i) they share an edge, or (ii) share a vertex. Let's say you call this amount $$W_{ij}$$.

Then the goal is to partition the mesh in such a way that (i) the partitions are of roughly equal size, and (ii) the sum of the $$W_{ij}$$ over all cut edges of the connectivity graph is minimal.

METIS (and in fact every reasonable other partitioning algorithm as well) allows you to attach edge weights to the connectivity graph. Depending on how exactly the partitioner defines the problem, these may be given by $$W_{ij}$$ or something like $$1/W_{ij}$$ (if the goal is to keep graph nodes -- i.e., cells -- together if the edge weight is large).

In practice, however, I don't know that people really do play these games. I suspect that you get more or less the same result treating all neighbors the same.

• So if I understand correctly you suggest to attach edge weights in order for the elements to share faces?If yes,I don't know if it is possible.I think only new METIS version supports element weights,however in the mesh file no element weights are included which means I have to edited the file by myself and for a big mesh it's a little bit difficult.However,I do not know how harmful is for the performance to use vertex and edge weights equall to a unit cost or if it acceptable to have elements sharing only a node. – spyros May 8 '20 at 0:36
• Well, METIS hasn't really changed since 1998, so "new" is a relative term on the METIS timeline :-) I know for a fact that METIS allows node weights. (Each node would correspond to a cell of the mesh.) I would be rather surprised if it didn't also allow edge weights in the graph. – Wolfgang Bangerth May 8 '20 at 12:37
• Ok maybe.However,the mesh file obtained by softwares like gmsh doesn't include weights which means you have to do it manually,right?Is that efficient? – spyros May 8 '20 at 13:40
• Right. The mesh is what it is. What the edge and cell weights are depends on what you want to do with it. Only you know what that is. (And yes, people load meshes all the time and partition from their own program. Here's our implementation: first, convert a mesh into a graph: github.com/dealii/dealii/blob/master/source/lac/… Then pass the graph to METIS: github.com/dealii/dealii/blob/master/source/lac/…) – Wolfgang Bangerth May 8 '20 at 14:45
• I see.Thank you.The last question is how to know the weights of the elements a priori?I mean you have a mesh file with thousands of elements(assume we talk for static partition for a linear elasticity model) how to know where to assign weights and the value of the weight?I read somewhere for such simple cases(static partitions) unweightened graphs work well(only by minimizing edge-cuts) – spyros May 8 '20 at 15:24