5
$\begingroup$

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: 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 ${\rm GF}(2)$ (which is not even mentioned in the paper).

  • 0
    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.2011-12-30
  • 0
    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.2011-12-30
  • 0
    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](http://infoscience.epfl.ch/record/164494/files/nscan11.PDF), 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.2011-12-30
  • 0
    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).2011-12-30
  • 0
    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](http://www.jstor.org/pss/2005827).2011-12-30

0 Answers 0