[Dune] Constrained load balance

[Aleksejs Fomins]

Dear Dune,

I have implemented support for Boundary Integral (BI) methods in CurvGrid some time ago. Such methods require coupling of each two pairs of boundary segments, or each boundary segment with each interior boundary segment, depending on formulation. The efficiency of such methods strongly depends on load balance across all processes. Here are the load balance criteria for BI in decreasing priority

1) Chunk of grid on each process should form a contiguous polyhedron
2) Polyhedron on each process touches the boundary, and the number of boundary segments should be as equal as possible among all processes
3) The element distribution on all processes is as equal as possible
4) Surface area of the polyhedron on each process should be as small as possible

For FEM, 2) can be ignored.

So far we have been using ParMetis. "ParMETIS_V3_PartKway" automatically optimizes 1), 3) and 4), and does exactly what we want for FEM. The above method also provides capabilities of constrained optimization, which can be used to get 2). However, the problem is that chunks are then no longer continuous. I have implemented it for CurvGMSHReader, and the result of such optimization is a highly scattered mesh with low connectivity.

I have contacted the developers of ParMetis, and was told that 1) is not actually done in ParMetis, and in the case of unconstrained optimization it is kind of side effect, whereas for constrained optimization it is not a given at all.

Has anybody come across constrained load balancing before?

Is there a trick to do it with ParMetis, or perhaps some other partitioning software?

Best regards,
Aleksejs