Faster rrlu decomposition?

[RaimelMedina]

Hi guys!

First of all, thanks for the amazing work and library!

I wonder if it is possible to further improve the speed of the current rrlu decomposition at the possible cost of reducing the accuracy. I've been trying to use the library (in python mostly) for large matrices (5000 x 15000) and large bond (~2000) dimensions and the time it takes to run some experiment is quite large (40 mins +).

I was reading this paper and I found the suggested algorithms to work quite fast and with accurate results. Essentially a chain of pivoted QR on columns of the matrix and columns of its transpose (this could be changed to a row pivoted LU I guess). Do you think this is worth the effort?

Happy to contribute if it is of interest to you!

[yurielnf]

Thanks!
Nice reference. This algorithm should be in fact very fast (although not provably rank revealing). To improve the quality of the pivot matrix I would follow a similar path suggested here:

1. Decompose AP=QR using lapack QR with column pivoting, to obtain the columns pivots J and the rank of A.
2. Decompose PA(:,J)=LU using lapack LU with row pivoting, to obtain the rows I.
3. Apply Algorithm 1 from Pan "On the existence and computation of rank-revealing LU factorizations", to refine I.

Let's go for it!

[yurielnf]

We have the basic implementation, which gives an interesting speed up:

Time (s) for decomposing a rank-(n/2)  matrix of size nxn:
n svd rrlu rrlu_new
500 0.051 0.06 0.017
1000 0.479 0.522 0.162
1500 1.607 1.887 0.506
2000 4.028 5.277 1.273
2500 7.778 15.118 2.646
3000 13.689 30.249 4.938
3500 22.085 50.551 8.4
4000 33.648 78.983 13.165
4500 47.44 113.228 22.499
5000 65.077 157.107 34.976