6
$\begingroup$

Feel free to suggest a different title, I'm not sure how to phrase this. I'm in the following somewhat specific situation:

I'm checking a conjecture which at the end of the day boils down to the computation of the rank of a large but very very sparse matrix with integer coefficients. The matrix is rectangular, of size roughly $n\times 2n$ for a somewhat scary value of $n$. Crucially, I know an upper bound $r$ for that rank, and crucially again the conjecture I'm trying to verify state that the rank is, in fact, exactly $r$. The bad news is that the conjectural $r$ is pretty close to $n$ (ie $n$ is more than a million, while $n-r$ is expected to be 34...)

What is the cleverest algorithm to check this ?

A fairly usual trick is to work modulo some small prime $p$ since it can only decreases the rank (so that if I do find exactly $r$ I know I'm done). Another idea is that it would be enough to find, maybe randomly, $r$ linearly independent rows or columns, and if $r$ was much smaller than $n$ I think it would indeed be much more efficient than actually computing the rank, but in my situation I'm not entirely sure it would. In particular, I'm wondering if there's a known way to turn the fact that the matrix at hand is almost of maximal rank to an advantage.

$\endgroup$
  • 1
    $\begingroup$ How large an $n$ do you find scary? And how sparse is sparse? $\endgroup$ – Andrej Bauer Sep 19 '19 at 15:25
  • 1
    $\begingroup$ $n$ is roughly 1.3 millions, and density is around 0.05. For the one I did handle by just computing the rank mod 17 using github.com/cbouilla/spasm, $n$ was about 600.000 and it took 40 hours. It seems for the largest one just computing the rank is gonna be tricky. $\endgroup$ – Adrien Sep 19 '19 at 16:31
  • 1
    $\begingroup$ How is it represented? Is each row and column a linked list? How long would it take you to make it into upper triangular form? Is it easy to sort the rows lexicographically? There might be algorithms almost linear in n in time if you have a good representation. Also, how useful is an approximation (e.g. quickly showing n-r less than 100)? Gerhard "Is Not Sparse With Ideas" Paseman, 2019.09.19. $\endgroup$ – Gerhard Paseman Sep 19 '19 at 19:38
  • 1
    $\begingroup$ I'm not sure if it is of any help, but if you managed to find $n-r$ independent vectors in $\ker A^T$, then you would be able to conclude that the rank of $A$ is at most $r$. $\endgroup$ – Federico Poloni Sep 20 '19 at 15:19
  • 1
    $\begingroup$ Reminds me of this paper where they had to use a little bit of strategy to compute a rank of a fairly large matrix: arxiv.org/abs/1510.02029 $\endgroup$ – Zach Teitler Sep 20 '19 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.