I'm looking for a parallel algorithm to compute ranks of huge, sparse binary matrices over F2 (say 10^5 x 10^5 with 10^7 ones in total).
Currently I'm doing this by packing 64 bits in a long and applying Gaussian elemination with XOR, swapping unneeded parts of the matrix to harddisk. While this goes rather fast (even such huge matrices take only a few days) I feel it's a pity that
A) I'm not using the fact that it's sparse, I feel this could give a huge improvement
B) I'm not using the fact that I have multiple processors available (1000+ in a GPU)
I wondered if anyone is aware of any better methods? I saw this paper: http://www.springerlink.com/content/h030156l561254r4/ but only computing the characteristic polynomial seems to be much more expensive than what I'm doing now. Or am I missing something? How should I compute this determinant polynomial efficiently?
Another approach would be working via http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.1632 and its derivates such as http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.1619, but this doesn't work for GF(2) [which is not even mentioned in the paper!].