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.



Row reduction of sparse matrices
The [LinBox project](http://www.linalg.org/) provides a C++ library which can effectively compute the rank of sparse matrices over finite fields.


You could also look at [Sage](http://www.sagemath.org/) 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](http://magma.maths.usyd.edu.au/magma/) can also do this.


