I am interested in computing the ranks of fairly large, the largest being of magnitude $10^6$ x $10^6$, sparse matrices whose entires are all 0, 1, or -1. I have been trying to use Matlab to accomplish this. In particular, my approach has been to use QR-factorization -- that is factoring my matrix $T$ as $TP=QR$ were $P$ is a permutation matrix, $Q$ is orthogonal, and $R$ is upper triangular -- and then counting the number of non-zero entries on the diagonal of $R$.
Using Matlab's built in QR function the following Matlab code computes the correct rank for some of my examples. (I have confirmed the rank for some of the smaller matrices against rank(full(T)).)
load(‘FILE_NAME.dat') T = spconvert(FILE_NAME); tic [Q,R,P]=qr(T); [m,n] = size(T); tol = max(size(T))*eps*abs(R(1,1)); r = 0; while (r<min(m,n) & abs(R(r+1,r+1)) >= tol) r = r+1; end tim=toc r
That said even for some of my smaller matrices this code seems fairly slow and memory intensive. For example, on one of these matrices that is ~70,000 x ~50,000 the above code takes numerous hours and most of the memory on a 64 GB server. (One thing I noticed is that if I save the Q, R, and P computed above to a .mat file the file size seems to grow quickly. For example, the .mat file is ~1 GB when initial matrix is ~15,000 x ~15,000)
Is there a better (quicker or less memory intensive) way to approach computing the rank of large sparse matrices? For example, a more effective way to implement QR-factorization or even a method entirely different from QR?