I just added a “v0.3” tag to my latest Minipart commit. It is shaping quite well, and is giving promising results at last. Compared to hMetis2, the results are very similar on average (2% better), although it’s still much much slower (5x).
A 2% quality improvement would be nothing to sneer at if I could improve the runtime, but this average hides a few interesting datapoints: some benchmarks show a 20% difference between hMetis and Minipart. I guess partitioning is not a solved problem yet.
There are a lot of things I want to try. Nowadays, you cannot just hand-tune your algorithm: it takes too much brain time, and our brain is bad at it anyway. I probably have a lot to gain by just trying all kinds of parameters automatically – what people have been doing with SAT solvers for a while. Or give the parameters to a good blackbox optimizer, like people now do for neural networks. Or maybe try machine learning, why not.
Less fun but equally important would be to implement and benchmark all the “good” algorithms I left aside: all other partitioners implement Fiduccia-Mattheyse and heavy-edge coarsening, but I didn’t try them yet. A lot of ideas from MLPart and hMetis have proven useful, and I expect to find some room for improvement here.