## 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. – S. Sra Jan 10 2011 at 19:53 also, several papers show up on google if you search for "compute rank finite field" – S. Sra Jan 10 2011 at 19:55

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.

-
 Thanks for the remark. I hope you don't mind if I ask a possibly stupid Magma question (the program I have is written in Magma). The current code constructs a vector space $V$ and a set of relations "rels", defines M = V/sub, and then returns "Dimension(V)". Supposing that the relations are not sparse and I am only interested in the dimension of M, is there any obvious inefficiency? (That is, when Magma "computes" M does it perform any slow computations that are superfluous to computing the dimension of M?) – Lavender Honey Jan 13 2011 at 21:06 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/… – Max Jan 15 2011 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.

-
 Thanks for the remark. – Lavender Honey Jan 14 2011 at 19:15