I have very large matrices that I would like to row reduce (I need to keep track of the steps and find a basis of the kernel/image, not just find the rank).

The good news is that I work mod 2 and the matrices are very sparse. The problem is their size, right now I have a beast that is roughly 3 millions x 1 million, but I expect much bigger, probably billions. I might have a thousand of those matrices that I would like to reduce eventually.

I found the linbox project that might be helpful, but before I wanted to know if anybody has a feeling whether or not this is realistic ? I could be using the Grid of my university which has "the combined processing power of 4,568 cores: 1,346 Intel cores, 3,222 AMD cores, with over 13.5TB of RAM and 1.2PB of disk space.". What do you think ?


  • $\begingroup$ from what I know of linbox, this seems to be extremely large and probably not realistic. I'd suggest that you contact the authors of linbox and ask them their opinion. $\endgroup$ – Brian Borchers Dec 6 '14 at 21:10
  • $\begingroup$ Yeah that's a good point, I saw there is even a google forum for asking them questions. $\endgroup$ – Bogdan Dec 6 '14 at 22:18
  • 1
    $\begingroup$ I believe that Sage uses linbox to do row reductions over GF(2), so you might find try using Sage to get a sense of what size problems it can handle and how much fill-in you're likely to see for your problems. $\endgroup$ – Brian Borchers Dec 6 '14 at 22:53
  • 1
    $\begingroup$ These kinds of problems (row reductions over GF(2)) are the final phase of quadratic sieve factorization schemes, though it sounds like you really are shooting for about twice as many columns as were needed for the record QS factorization. $\endgroup$ – hardmath Dec 7 '14 at 2:12
  • 2
    $\begingroup$ "I work mod 2" means the content are just 0 and 1? Then the row reduction operations are just XOR (and swap), right? To harness the binary nature, I guess you should try to find a tool that specifically does that, not just a general solver. $\endgroup$ – justhalf Dec 9 '14 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.