I'm using METIS with Conan from the Conan Center, so it's METIS 5.2.1.
I have a mesh that has 297 elements, so those are the 297 nodes of the graph and I want to partition it into 64 parts for distributing the workload on 64 different MPI processes and more (for scalability study purpose).
I was expecting METIS to be able to partition my graph into something like 41 partitions with 5 nodes on it and 64-41=23 partitions with 4 nodes on it (since 297 = 541 + 4 (65-41)). But instead, I see several messages in my terminal saying :
***Cannot bisect a graph with 0 vertices!
***You are trying to partition a graph into too many parts!
From what I understand looking at METIS code, during the initial partitioning phase, a recursive bisection algorithm is performed and during this the recursive calls end up with calling a bisection on a subgraph that has 0 nodes. And from Multilevel
k-way Partitioning Scheme
for Irregular Graphs - Karypis, Kumar :
"The k-way partitioning problem is most frequently solved by recursive bisection. ... There are a number of advantages of computing the k-way partitioning directly (rather than computing it successively via recursive bisection). First, the entire graph now needs to be coarsened only once, reducing the complexity of this phase to O(|E|) down from O(|E| log k). Second, it is well known that recursive bisection can do arbitrarily worse than k-way partitioning [27]. Thus, a method that obtains a k-way partitioning directly can potentially produce much better partitionings. ... In our algorithm, the k-way partitioning of Gm is computed using our multilevel bisection algorithm [16]. Our experience has shown that our multilevel recursive bisection algorithm produces good initial partitionings and requires a relatively small amount of time as long as the size of the original graph is sufficiently larger than k."
So I guess, METIS does what the paper says, but I feel like there should be a way of going around this recursive bisection during the initialisation phase ? To handle more cases of partitioning ? To do this "direct k-way partitioning" ? Is there ?
And more, I feel like METIS exiting the calls to METIS_PartGraphKWay without raising an error saying that the partitioning is incomplete and should not be used as such is dangerous, so I decided to report it in an issue here.
Hello there,
I'm using METIS with Conan from the Conan Center, so it's METIS 5.2.1.
I have a mesh that has 297 elements, so those are the 297 nodes of the graph and I want to partition it into 64 parts for distributing the workload on 64 different MPI processes and more (for scalability study purpose). I was expecting METIS to be able to partition my graph into something like 41 partitions with 5 nodes on it and 64-41=23 partitions with 4 nodes on it (since 297 = 541 + 4 (65-41)). But instead, I see several messages in my terminal saying :
From what I understand looking at METIS code, during the initial partitioning phase, a recursive bisection algorithm is performed and during this the recursive calls end up with calling a bisection on a subgraph that has 0 nodes. And from Multilevel k-way Partitioning Scheme for Irregular Graphs - Karypis, Kumar : "The k-way partitioning problem is most frequently solved by recursive bisection. ... There are a number of advantages of computing the k-way partitioning directly (rather than computing it successively via recursive bisection). First, the entire graph now needs to be coarsened only once, reducing the complexity of this phase to O(|E|) down from O(|E| log k). Second, it is well known that recursive bisection can do arbitrarily worse than k-way partitioning [27]. Thus, a method that obtains a k-way partitioning directly can potentially produce much better partitionings. ... In our algorithm, the k-way partitioning of Gm is computed using our multilevel bisection algorithm [16]. Our experience has shown that our multilevel recursive bisection algorithm produces good initial partitionings and requires a relatively small amount of time as long as the size of the original graph is sufficiently larger than k."
So I guess, METIS does what the paper says, but I feel like there should be a way of going around this recursive bisection during the initialisation phase ? To handle more cases of partitioning ? To do this "direct k-way partitioning" ? Is there ? And more, I feel like METIS exiting the calls to METIS_PartGraphKWay without raising an error saying that the partitioning is incomplete and should not be used as such is dangerous, so I decided to report it in an issue here.
Here is a reproducible test of this example :