# Mesh domain decompositions / mesh partitioning

I have some experience with mpmetis from METIS. It is pretty good software which offers unstructured mesh grid partitioning. But obtained results always minimize edgecuts or total communication volume. So splitting simple mesh grid into 2 parts gives me about 50 to 50% of mesh nodes in each part.

I am looking for software (or better C++ library) which gives me possibility to split mesh into unequal parts - for example 10 to 90% of nodes in each part. It will be nice if I can decide about divide ratios.

• Are you sure Metis (or ParMetis) doesn't provide this feature? At least it offers to weight the entities of your mesh. Mar 27, 2012 at 21:51
• Well, I didn't think about weights. Thanks for the hint - I will check that. Mar 27, 2012 at 22:10
• You can download the manual: glaros.dtc.umn.edu/gkhome/metis/metis/download and look up 3.5 "Partitioning for heterogeneous parallel computing architectures". This should be your starting point. Mar 27, 2012 at 22:27
• @Martin - you might as well write up your first comment as an answer :) Mar 28, 2012 at 0:25
• @Martin: I'd even say write up your first two comments as a single answer. Mar 28, 2012 at 2:58

As can be found in the manual for METIS (and as well for parMETIS), available on http://glaros.dtc.umn.edu/gkhome/metis/metis/download in section 3.5 "Partitioning for heterogeneous parallel computing architectures", METIS does support non-equal partitioning of elements on different processes.

The constitutive argument in the function calls "METIS_PartMeshDual" and "METIS_PartMeshNodal" is "tpwgts". The entries of that array are supposed to be a partition of unity [*], that indicate the weight each process should be assigned eventually. By default, the weight of all elements is assumed to be uniformly 1.

[*] i.e., the entries are floating-point numbers that sum up to 1.0. The manual seems to ignore floating-point error at this condition.

• Is it really true that the node weights need to add up to one? Usually, when doing these sort of things, all the partitioning algorithm wants to do is make sure that the sum of node weights on every processor is roughly the same. From an algorithmic viewpoint, it's not really necessary for the sum to be one. Mar 28, 2012 at 18:58
• I have just cited the manual. The restriction on the weights only applies to the proportion you want to assign to each process, that might rescale the weight of the nodes. These process weights are assumed to add up to 1. for reasons unknown to me. Mar 29, 2012 at 18:52

Have you tried scotch?

"SCOTCH is a project carried out within the Satanas team of the Laboratoire Bordelais de Recherche en Informatique (LaBRI). It is part of the ScAlApplix project of INRIA Bordeaux - Sud-Ouest.

Its purpose is to apply graph theory, with a divide and conquer approach, to scientific computing problems such as graph and mesh partitioning, static mapping, and sparse matrix ordering, in application domains ranging from structural mechanics to operating systems or bio-chemistry."

get it here: scotch site,

have a look at this as well: scotch-metis tutorial + comparison