Why dual graph for mesh partitioning

Question

Software such as ParMetis or PTScotch partition a graph. When one wants to use it for mesh partitioning (for example for FEM), a dual graph whose vertices represent cells of the original mesh is usually constructed first. This dual graph is then partitioned. I was wondering why one cannot simply interpret the connectivity of the input mesh as a graph directly - mesh nodes are graph vertices and mesh edges are also graph edges. This would assume that the list of mesh edges is built by client application before the call to the partitioning routine.

If I understand correctly, the cut through a dual graph will contain whole faces of adjacent mesh cells belonging to different partitions, while cut through the mesh (seen as a graph) will be less pretty in the sense that only some nodes of an element face might become ghost nodes. In addition, the number of mesh edges (especially in 3D) will probably be much higher than the number of cells. Apart from that, I don't see what are the advantages of using the first or the second approach. Can anyone comment on this?

I am aware of the fact that (Par)Metis has a function to construct a dual graph. My question is 'why', not 'how'. I'm mainly interested in mesh partitioning for FEM.

Answer 1

The most common way to write finite element software is to make a non-overlapping partition of elements with interface vertex ownership resolved using some rule (or via hypergraph partitioning, which is more expensive). To create a globally-assembled stiffness matrix, this involves communication of entries to the process that owns the vertex. Residual evaluation and matrix assembly does work based on elements, but the solve (using sparse iterative methods) does work based on the vertices.

An alternative is to create a non-overlapping vertex partition and create a ghost layer of elements. Those interface elements will be integrated redundantly (from each side) but there is no communication to assemble the matrix.

This tends to scale somewhat better for low-order elements. High-order elements have chunky interfaces and are generally more efficient to integrate using a non-overlapping element partition. Pick your method based on how you manage your mesh and the cost tradeoffs for the discretization you choose.