search

cheind / py-lapsolver

Fast linear assignment problem (LAP) solvers for Python based on c-extensions
MIT License
154 stars 24 forks source link

Parallel Algorithm #4

Closed rwolst closed 2 years ago

rwolst commented 5 years ago

This is certainly the fastest LAP solver for Python that I used (by a fair margin). I was wondering if you know of any parallel extensions to the algorithm (that are well accepted) for the LAP. I Googled but couldn't find any popular approach.

If there is, I would be interested in extending the project with OpenMP.

It seems like this may be a good review of the methods: https://pdfs.semanticscholar.org/f202/410bbc322784673f707dd35cd3220d4bca47.pdf

cheind commented 5 years ago

Hi,

that would be a welcome addition!

I tried to parallize with OpenMP in the past, but it didn't work for me. I might have done something wrong and/or didn't pay too much attention during coding. Just recently closed #2, which was due to a left-over from the OpenMP test. I also wanted to use Eigen in the core code, as in my experience it simplified matrix related code and often boosted its performance as well.

There are unit tests and benchmarks in lapsolver that should help you with correctness and performance analysis.