Kernel of a Sparse Matrix

Question

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?

Answer 1

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.