Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $p$ be prime (of size roughly $100$, say). Suppose that $M$ is a matrix with coefficients in $\mathbf{F}_p$ with roughly $An$ rows and $n$ columns, where $A>1$ is some fixed small constant. Suppose, moreover, that

  1. Every row of $M$ has at most $B$ non-zero entries, which are all $\pm 1$, for some small $B$.
  2. The rank of this matrix is small, say, of order $O(\sqrt{n})$ (this may or may not be relevant.)

I am interested in computing the rank of $M$. Does the fact that $M$ is sparse imply that there are relatively efficient ways of computing this rank? How large should I expect to be able to take $n$ and still be able to compute the rank? The current program I am running (which was kindly written [very quickly without a view to optimization] for me by someone else) chokes up with $n \sim 5000$ or so, and for $n \sim 4000$ seems to take around $20$ minutes.

share|improve this question
    
you might find: linalg.org useful. –  Suvrit Jan 10 '11 at 19:53
    
also, several papers show up on google if you search for "compute rank finite field" –  Suvrit Jan 10 '11 at 19:55

2 Answers 2

up vote 3 down vote accepted

The LinBox project provides a C++ library which can effectively compute the rank of sparse matrices over finite fields.

You could also look at Sage which should also allow this, but I am not sure whether they have effective implementations for this particular case. If you have access to it, then Magma can also do this.

share|improve this answer
    
I am not an expert in Magma at all (I am usually working with GAP instead). But a quick look at the Magma handbook revealed the existence of a Rank function -- did you try that? magma.maths.usyd.edu.au/magma/handbook/text/261#2441 –  Max Horn Jan 15 '11 at 11:52

Yes, sparsity should help a lot, though since your entries are in $\mathbb{F}_p$ you might not be as likely to find off-the shelf code as for real numbers. Still, you will find a lot of material if you look for "Sparse LU" (you can adapt Tim Davis' code, which is available), or, better yet, googling for "Sparse LU finite field" will give you the right pointers.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.