New Feature : A very fast algorithm for computing matrix rank

[touqir14]

🚀 Feature

I have devised an LUP based matrix rank computing algorithm that outperforms significantly the standard Numpy's matrix_rank function and PyTorch's GPU accelerated matrix_rank algorithm for most cases. For instance, for large matrices it offers a speedup of at least 200 times over Numpy's matrix_rank and 10 times over PyTorch's matrix_rank function as tested on Google Colab running on Tesla K80. See the benchmarks. Unlike the LU factorization, LUP is stable in practice and I have thoroughly tested the correctness of my implementation.

Motivation

Computing the matrix rank can be rather slow, particularly if one deals with large matrices and needs to run multiple times for at least tens of times. This motivated me to come up with a much faster approach than the standard rank computing methods.

Pitch

I would like to consider the prospect of implementing this as a PyTorch function. My implementation uses scipy's LUP function and a couple of Cython optimized functions along with the standard Numpy matrix operations. When GPU acceleration is enabled, it additionally uses PyTorch's LUP function.

Let me know if you need to know more about the algorithm's specifics and testing/benchmarks.

cc @mruberry @rgommers @vincentqb @vishwakftw @SsnL @jianyuh

[l1t1]

good.

[rgommers]

@touqir14 rather than do PyTorch and SciPy discussions in parallel, it would be good to start in one place and get something about precision written up.

[touqir14]

I will put up a document with the correctness test results. @rgommers

[touqir14]

I have written a post comparing the success rates of LUP-rank-computer and numpy.linalg.matrix_rank

[mruberry]

Hey @touqir14, that's pretty cool. I would encourage you to make your work available to the community in your github, so if someone who uses PyTorch wants to use it they can, and to start by working with the SciPy maintainers, if they're interested, in translating your work into a framework.