Optimisations for rectangular matrices

[AlexeyG]

Hi,

I was looking for a fast linear assignment solver and came across this project. Great work! Thank you.

It compares well against Scipy's linear_sum_assignment on square matrices, but is significantly worse on rectangular matrices.
The implementation appears to not support rectangular matrices out of the box, so to test it against Scipy I padded the cost matrix with high values to make it square.

In this setting the algorithm this implementation was much slower than the Scipy implementation on rectangular matrices (and still faster than Scipy implementation on the padded matrix).

I was wondering if the this algorithm could be made to work efficiently on rectangular matrices, or whether there are perhaps some fundamental limitations that would prevent this.

Thanks,
Alexey

[AlexeyG]

def get_mat(n, m = None):
  return np.random.normal(size=(n, m or n))

mat = get_mat(5000, 300)
mat_padded = np.concatenate([mat, np.full((5000, 5000 - 300), 10.)], axis=1)

%timeit scipy.optimize.linear_sum_assignment(mat)
# 23.1 ms ± 470 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit lapjv.lapjv(mat_padded)
# 345 ms ± 56.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit scipy.optimize.linear_sum_assignment(mat_padded)`
# 566 ms ± 56.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)