[eigen] fast calculation of matrix rank |

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

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: [eigen] fast calculation of matrix rank*From*: Pieter Eendebak <pieter.eendebak@xxxxxxxxx>*Date*: Fri, 29 Jan 2016 23:24:34 +0100*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=431VomY2gRDpcZsusuJIrc5OumLXV0PoxsY/59tJrsY=; b=e8gcSm3Y1sHpG9dvA31ihrSkBJV9i6O9jM77L0+Y5tkF51mW4OEsYHiI0MX1n6nMTC rnkzcVGqofRJw/88DEFvIWIiTMjZOttVrJG7CwINKAAuGpGmRzfZe2ZnxCcpy3alPyD6 gkcNwRfzu22yVyTgWzJUaRDPQejZoJojzp8eWQFgrtQNmH/rNkH87ehKsPGkKoc9J4mT BuCqT2H3NqjWY0wpSr28A4iDqdB8T2HVvqeDCiEFUPIhUf0/cyqDY5T+7Ya2Xb/fV8Vf /gXHJOvyS9LbSWjPHzHSRiiRi0bIf0sLWtFawZa50LgN9NMwxgIVQJt+VUHpMBVM6ckg Nu6Q==

Hi,

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,

Pieter

The matrices share a common block Most of matrices

**Follow-Ups**:**Re: [eigen] fast calculation of matrix rank***From:*marco stamazza

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Blocked QR with column pivoting.** - Next by Date:
**[eigen] SelfAdjointEigenSolver on rank-defficient matrices** - Previous by thread:
**Re: [eigen] modifying the colPivotQR function** - Next by thread:
**Re: [eigen] fast calculation of matrix rank**

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