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.