2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ PETSc is fast, scalable, has C wrappers and can perform these tasks. $\endgroup$
    – user20857
    Commented Sep 6, 2016 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
    Commented Sep 6, 2016 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$
    – user20857
    Commented Sep 6, 2016 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
    Commented Sep 11, 2016 at 6:58

1 Answer 1

Reset to default
2
$\begingroup$

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/

Improve this answer
$\endgroup$
1
  • $\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
    Commented Sep 11, 2016 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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