CODEWITHSUNDEEP
c++windowslinear-algebrasparse-matrix
ReverseFlowControl
ReverseFlowControl

Reputation: 826

What is the fastest way/library to calculate the rank of a matrix in C++

What library computes the rank of a matrix the fastest? Or, is there any code out in the open that does this fairly rapidly?

I am using Eigen3 and it seems to be slower than Python's numpy rank function. I just need this one function to be fast, absolutely nothing else matters. If you suggest a package everything but this is irrelevant, including ease of use.

The matrices I am looking at tend to be n by ( n choose 3) in size, the entries are 1 or 0....mostly 0's.

Thanks.

Edit 1: the rank is over R.

Upvotes: 4

Views: 2680

Answers (1)

Matthew Gunn
Matthew Gunn

Reputation: 4519

In general, BLAS/LAPACK functions are frighteningly fast. This link suggests using the GESVD or GESDD functions to compute singular values. The number of non-zero singular values will be the matrix's rank.

LAPACK is what numpy uses.

In short, you can use the same LAPACK library calls. It will be difficult to outperform BLAS/LAPACK functions, unless sparsity and special structure allow more efficient approaches. If that's true, you may want to check around for alternative libraries implementing sparse SVD solvers.

Note also there are multiple BLAS/LAPACK implementations.

Update

This post seems to argue that LU decomposition is unreliable for calculating rank. Better to do SVD. You may want to see how fast that eigen call is before going through all the hassle of using BLAS/LAPACK (I've just never used eigen).

Upvotes: 4

Related Questions