I have a matrix, $M$, size of approximately $20\times 25$, over a polynomial ring $\mathbb{Q}[x_1, \cdots, x_n]$ and a number $r$ such that I would like to test whether or not there exist values for the $x_i$ such that the $\text{rank }M\leq r$.

The most natural approach to me is to take the $r+1 \times r+1$ minors and consider the ideal that these minors generate. However, the issue is that if I wish to test rank $r = 6$, for example, the sheer number of minors and the following Groebner basis calculation take an exceedingly long time to compute (on the order of weeks in some cases). I am currently using SageMath software to do these computations.

I should state that I have already leveraged putting the matrix in a partial Smith normal form and the sparsity of matrix, when possible.

Are there any other algorithms I could employ in addition to (or in lieu of) the above strategy?

cannotbe made less than $r$. $\endgroup$dohave solutions satisfying the few minors you tested. Such solutions correspond to matrices with some minors forced to be zero. If you are lucky (which has often been the case in my experience), then you may find that the matrices actually have small rank. $\endgroup$