# ParMETIS (4.0.3) PartKway returns discontiguous partitions with "large" number of MPI tasks

Dear all,

I am using ParMETIS (version 4.0.3) to partition in parallel

the dual graph of a finite element mesh with 8.75M tetrahedra.

In particular, I build the dual graph on my own, and then

call ParMETIS graphpartkway subroutine to partition it into

the same number of parts as MPI tasks involved in the parallel

computation. The dual graph is constructed in such a way that

two vertices are neighbours if and only if the corresponding tetrahedra

share a face. I am using ncon==1, no vertex/edge weights nor tpwgts,

and ubvec=1.10.

With this set-up, I am obtaining discontiguous partitions

with 1024 MPI tasks/partitions and beyond. I am aware that

ParMETIS 4.0.3 does not ensure contiguous partitions, but ...

1) Is there any algorithm set-up that favours contiguous

partitions? I have tried defining NGR_PASSES to 20 (instead of 4)

in defs.h without success. I also tried to replace the

parallel recursive bisection at the coarsest level by a replicated

on all processors METIS 5.x partkway with METIS_OPTION_CONTIG enabled,

also without success (i.e., it seems uncoarsening/refining to be

the source of discontiguity).

2) Would it be so hard to write a message-passing code that tries to

enforce contiguous partitions afterwards as it is done in METIS 5.x

when METIS_OPTION_CONTIG is enabled ?

Find at

http://www3.uji.es/~martina/part117_discont.png

a picture showing how does a discontiguous partition

looks like. It is the local finite element mesh corresponding

to part. id 117. Note that in the bottom-right corner, there are two

tetrahedra sharing only one corner; these two tetrahedra are

DISCONNECTED in the dual graph. This kind of situation can lead to

singularities in the solution of

local Neumann problems in domain decomposition solvers (the ones that

are fed by the finite element mesh partition computed by ParMetis).

Thanks for your support.

Best regards,

Alberto.

## RE: ParMetis can produce

ParMetis can produce disconnected partitions as it does not enforce any connectivity constraints.

## RE: RE: ParMetis can produce

That's it? There is nothing one can do at least to favour contiguous partitions via e.g., parameter values?

## RE: Unfortunately there is none.

Unfortunately there is none. The serial Metis does have that option, but not ParMetis.

## RE: Unfortunately there is none

Thanks for your response.

I have been taking a look at the code that enforces contiguous partitions in METIS, and I have the feeling that it would be quite hard to develop this code within ParMETIS given the constraints imposed by the distributed-memory environment (due to the lack of a global view of the problem). Isn`t it? Have you got any idea about how this problem could be solved in an efficient way?

Thanks.

Best regards,

Alberto.

## RE: Moving Metis' algorithm in

Moving Metis' algorithm in ParMetis is non-trivial (this is why it is not there).

As far as an "engineering" solution that you may want to try out, is to do the partitioning using some form of a repeated k-section, in which k is > 2 and < # of final partitions. However, if your mesh is rather small compared to the # of partitions that you want to compute, then the above may be of little help.

## RE: Thanks for your

Thanks for your response.

This is precisely the "solution" that we had in mind. In particular, in a first partitioning level, use the minimum number of MPI tasks such that the problem fits into available memory, to generate as many # of partitions. In a second partitioning level, call METIS whithin each MPI task (with METIS_OPTION_CONTIG enabled), to generate the rest of partitions.

Best regards,

Alberto.