I am looking for the subject. The size of matrices will be around 1000x2000 elements with linear amount of ones (say, 6000 ones in the whole matrix).

The operations I will use the most:

  • iterating over elements of particular column;
  • iterating over elements of particular row;
  • getting submatrix by columns;
  • solving undetermined linear system (over Galois field $\mathbb F_2$).

Before starting to implement it myself I want to ask the community about the existing libraries. Also if you have some ideas on implementation - feel free to share.

P.S. Memory usage is not of much importance for me.

  • 1
    $\begingroup$ PETSc is fast, scalable, has C wrappers and can perform these tasks. $\endgroup$ – Spencer Bryngelson Sep 6 '16 at 15:14
  • $\begingroup$ I briefly looked at PETSC manual. Are you sure it can work with binary matrices. My feeling is that it is only for real matrices... $\endgroup$ – Yauhen Yakimenka Sep 6 '16 at 20:45
  • $\begingroup$ You are correct that it does not have a direct handling for binary matrices. Your problem is not especially large, are you sure that this deficiency is prohibitive? $\endgroup$ – Spencer Bryngelson Sep 6 '16 at 21:47
  • $\begingroup$ @Spencer Bryngelson, the last point is very specific (Galois field), and to my knowledge general sparse matrices packages do not have it. $\endgroup$ – BrunoLevy Sep 11 '16 at 6:58

CADO-NFS [1] (implementation of the Number Field Sieve algorithm for factoring integers) has an implementation of sparse binary matrices and linear solve over specific fields (I am not 100% sure it has the Galois field that you need, but it probably has something at least similar).

[1] http://cado-nfs.gforge.inria.fr/

| cite | improve this answer | |
  • $\begingroup$ This looks much more promising. I will dig in the library to see if I can find ready-made solution. Thanks! $\endgroup$ – Yauhen Yakimenka Sep 11 '16 at 10:16

Your Answer

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

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