# Fast C++ implementation of sparse binary matrices

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.

• PETSc is fast, scalable, has C wrappers and can perform these tasks. – Spencer Bryngelson Sep 6 '16 at 15:14
• 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... – Yauhen Yakimenka Sep 6 '16 at 20:45
• 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? – Spencer Bryngelson Sep 6 '16 at 21:47
• @Spencer Bryngelson, the last point is very specific (Galois field), and to my knowledge general sparse matrices packages do not have it. – BrunoLevy Sep 11 '16 at 6:58

## 1 Answer

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).

• This looks much more promising. I will dig in the library to see if I can find ready-made solution. Thanks! – Yauhen Yakimenka Sep 11 '16 at 10:16