# Kernel of a Sparse Matrix

Given a sparse rectangular matrix $A$ (let's say, with dimension $n,m$ and number of non-zero elements $O(n)\sim O(m)$) with entries in $\mathbb Z/2\mathbb Z$ I'm looking for a basis of the kernel as a $\mathbb Z/2\mathbb Z$ vectorial space.

I know that applying Gauss I can easily find them, but it doesn't use the hypothesis that $A$ is sparse, and all the libraries I found use Gauss, and are optimized for dense matrices.

I'm asking you, is there an algorithm (or a C++ library) that does this task using the sparse structure of the matrix, and performs better than Gauss?

In general, which library will let me work with matrices on an arbitrary field?

• How big are your matrices? – Wolfgang Bangerth Oct 11 '15 at 13:43
• n = 4 * s, where s is the length of an electronic message, so it can be small (s~500 for text mails/sms) or very large (the size of an attachment). Let's say that for my purpose, s~10^4 – user49870 Oct 11 '15 at 13:53

To address your last question, the library LinBox contains code for linear algebra (dense and sparse) over finite fields. There is an example of computing the basis of the nullspace of a sparse matrix over $\mathbb{Z}/p^k\mathbb{Z}$.
If you were doing your computation over $\mathbb{R}$, I would have suggested to use a sparse singular value decomposition to get the right singular vectors corresponding to the zero (or smallest) singular values.