I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java:
Unfortunately the speed is not adequate for my use case, so I'm looking to improve this. I have added some slow tests to the repo that I will use to measure the performance improvements.
I have further done some research and came up with the following three options to improve performance:
- Parallelizing Edmonds Blossom, in particular reference is this implementation
- Variable Dual Updates and the use of Priority Queues as described in Blossom V
Based on the Blossom V paper I'm expecting at least improvements in the order of one or two magnitudes. The reference to the parallel approach is unfortunately no longer available.
Now before I get started on in-depth reading and more coding I have some questions that I hope will help me channel my efforts:
- Are there any other algorithmic / implementation improvements available to increase performance significantly?
- Are there any papers available on parallelizing the algorithm?
- I want to do iterative improvements, do you see any reason why I can not add the suggested improvements independently?
- What is the best order to add the improvements? What approach has the most value (complexity of implementation vs speed improvement) in your opinion (assuming ~10 cores) and why?
- Is there code refactoring / separation you would recommend doing before starting on optimization?
Disclaimer / Misc:
I'm a big believer in Open Source and will keep the repository up with all the improvements I am making to it!
Found a great paper on the Blossom V performance and where to best add parallelization here. That somewhat answers question (2).
I'm now wondering if I should start from scratch and just implement Blossom V.