Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking for a parallel algorithm to compute ranks of huge, sparse binary matrices over $\Bbb F_2$ (say $10^5 \times 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: 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 and its derivates such as, but this doesn't work for ${\rm GF}(2)$ (which is not even mentioned in the paper).

share|cite|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

Your Answer


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

Browse other questions tagged or ask your own question.