3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ How big are your matrices? $\endgroup$ Oct 11, 2015 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$
    – Exodd
    Oct 11, 2015 at 13:53

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.