Row reduction of sparse matrices - MathOverflow

Row reduction of sparse matrices

2011-01-10T19:38:21Z

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

Every row of $M$ has at most $B$ non-zero entries, which are all $\pm 1$, for some small $B$.
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.

Answer by Igor Rivin for Row reduction of sparse matrices

2011-01-10T20:05:25Z

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.

Answer by Max for Row reduction of sparse matrices

2011-01-10T20:47:04Z

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.