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?

  • $\begingroup$ How big are your matrices? $\endgroup$ – Wolfgang Bangerth Oct 11 '15 at 13:43
  • $\begingroup$ 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 $\endgroup$ – 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.

| cite | improve this answer | |

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.