# Row reduction of sparse matrices

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.

-
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

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.