Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!].

share|improve this question
    
Do you have an idea what the rank is, in relation to the order of the matrix? Knowing that the matrix is sparse doesn't give much of an idea how many rows might be required to find one that is linearly dependent on the others. I have in mind to do a block reduction, and the key would be finding a largeish set of rows that are independent (then using that to define an invertible block). Yes, the characteristic polynomial is too expensive and brings a lot of unneeded/unwanted information. –  hardmath Dec 30 '11 at 17:08
    
Variable, usually rank 10-100% of the matrix size, but this is not absolute. I have no particular interest in the extremely low-rank cases, if that is what you're asking for. –  user1111929 Dec 30 '11 at 18:26
    
The literature on factoring by quadratic residues treats somewhat similar problems, although the context there provides matrices that are nearly full rank (by limiting the number of rows as a matter of computational cost). See for example this 1988 paper by Lenstra and Manasse, Compact incremental Gaussian elimination over Z/2Z, which has a citation to a 1984 paper by Parkinson and Wunderlich, "A compact algorithm for Gaussian elimination over GF(2) implemented on highly parallel computers", for a similar algorithm. –  hardmath Dec 30 '11 at 19:14
    
GF(2) is a finite field. The paper by Dumas & Villard indeed addresses GF(2). Wiedemann's algorithm works for fields of any characteristic (and for rings). –  user2468 Dec 30 '11 at 19:31
    
Also, if your matrices are sparse then you should choose an iterative algorithm (e.g. Wiedemann, Lancsoz) rather than elimination. GE will result in a fill-in. –  user2468 Dec 30 '11 at 19:33
add comment

1 Answer

If your matrix is binary, its rank is the number of unique rows minus the number of rows with only 0s on them, isn't it?

Then the fast algorithm is pretty obvious. Each thread i will be in charge of finding whether or not there is a duplicate row j of the row i in the matrix (j > i).

share|improve this answer
1  
How about the 3x3 matrix with zeros only on the diagonal (ones otherwise). All three rows are unique, and there are no rows with only zeros. But the rank is two, as the third row over $\mathbb{Z}_2$ is the sum of the first two rows. –  hardmath Dec 30 '11 at 17:03
    
Indeed, as @hardmath indicated, this is absolutely not a valid algorithm. –  user1111929 Dec 30 '11 at 18:28
    
This is not fast. Thread workload will be extremely unbalanced. –  user2468 Dec 30 '11 at 19:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.