[eigen] fast calculation of matrix rank

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]


Using Eigen I am trying to calculate the matrix rank of a large number of arrays. So far I have used FullPivLU but this is too slow for my application. The alternative ColPivHouseholderQR is faster, but still not fast enough. What are options for calculating the rank faster? My matrices have size 64x92 and integer elements (+1 or -1)..

There is one additional fact that might used. All matrices are of the form

A_i = [A B_i]

with A a common submatrix of the A_i.

I can then calculate the rank of A_i in the following way. First perform ColPivHouseholderQR on A:

AP =  QR

and determine the matrix rank of A as r0. Then for each matrix A_i we calculate

X_i = Q^(-1) A_i P^(-1)

The rank of X_i is equal to the rank of A_i. Next, take the submatrix

Y_i = X_i[r0:, r0:]

Then rank(A_i) = rank(X_i) = rank(A) + rank(Y_i).

Instead of calculating the rank of A_i we only have to calculate the rank of Y_i, which is much smaller in size than A_i. I have checked that calculation of the ColPivHouseholderQR decomposition of the Y_i matrices is indeed faster. However, the multiplication Q^(-1) A_i P^(-1) is almost as expensive as the decomposition on the original array X_i. Is there a way I can use the common submatrix in the rank calculations without performing the multiplication?

With kind regards,


 The matrices share a common block Most of matrices 

Mail converted by MHonArc 2.6.19+ http://listengine.tuxfamily.org/