Row reduction of sparse matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T08:40:41Z http://mathoverflow.net/feeds/question/51684 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51684/row-reduction-of-sparse-matrices Row reduction of sparse matrices Lavender Honey 2011-01-10T19:38:21Z 2011-01-14T19:27:51Z <p>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</p> <ol> <li>Every row of $M$ has at most $B$ non-zero entries, which are all $\pm 1$, for some small $B$.</li> <li>The rank of this matrix is small, say, of order $O(\sqrt{n})$ (this may or may not be relevant.)</li> </ol> <p>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.</p> http://mathoverflow.net/questions/51684/row-reduction-of-sparse-matrices/51689#51689 Answer by Igor Rivin for Row reduction of sparse matrices Igor Rivin 2011-01-10T20:05:25Z 2011-01-10T20:05:25Z <p>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. </p> http://mathoverflow.net/questions/51684/row-reduction-of-sparse-matrices/51697#51697 Answer by Max for Row reduction of sparse matrices Max 2011-01-10T20:47:04Z 2011-01-10T20:47:04Z <p>The <a href="http://www.linalg.org/" rel="nofollow">LinBox project</a> provides a C++ library which can effectively compute the rank of sparse matrices over finite fields.</p> <p>You could also look at <a href="http://www.sagemath.org/" rel="nofollow">Sage</a> 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 <a href="http://magma.maths.usyd.edu.au/magma/" rel="nofollow">Magma</a> can also do this.</p>