Efficient algorithms for dealing with linear algebra over the rationals

Question

I'm an academic mathematician. While trying to verify a counterexample to something in my research, the following computational problem has arisen:

Fix a vector space $V = \mathbb{Q}^n$. Here $n$ is something on the order of $20,000$. I have a procedure that spits out a sequence of vectors $\vec{v}_1,\vec{v}_2,\ldots$ in $V$. The vectors $\vec{v}_i$ all have integer entries; these entries are bounded in size (by something on the order of 20 or 30). For each $k \geq 2$, I need to decide if $\vec{v}_k$ is in the $\mathbb{Q}$-span of the set $\{\vec{v}_1,\ldots,\vec{v}_{k-1}\}$.

What algorithm should I use for this? The naive thing to do would be to just use Gauss-Jordan elimination (or, if I want to mostly stick with integers, compute the Hermite normal form). However, experiments I have done show that the size of the numbers that arise when you do this explode in complexity even for much smaller problems. This accords with stuff I have found while searching the literature, though I don't know the computer science literature very well and have trouble determining the state of the art in stuff like this.

Answer 1

One trick I've seen elsewhere is to pick a random prime $p$, reduce everything modulo $p$, and check whether the vectors are linearly independent over $(\mathbb{Z}/p\mathbb{Z})^n$. If $p$ is not a divisor of any of the entries of the vectors, and if $v_k$ is not in the $(\mathbb{Z}/p\mathbb{Z})^n$-span of $v_1,\dots,v_{k-1}$, then $v_k$ isn't in the $\mathbb{Q}$-span of $v_1,\dots,v_{k-1}$, either. By picking $p$ to be large enough (larger than the largest of the vector-entries), you can be sure $p$ won't be a divisor of any of the entries.

So, this provides a pre-test you can use. You run the pre-test first (working modulo $p$), and if it outputs "linearly independent", then you don't need to run the expensive $\mathbb{Q}$-span test; on the other hand, if it outputs "linearly dependent", then you do need to do the expensive $\mathbb{Q}$-span test (e.g., Gaussian elimination).

And, I think there's a heuristic argument that if $p$ is random and large enough, then if it's $\mathbb{Q}$-independence then with high probability (over the choice of $p$) it'll be $(\mathbb{Z}/p\mathbb{Z})^n$-independent, too. Or something like that. But it's just a heuristic and no guarantee that it'll work for all situations.

I hope I have this right. I'm going from memory so I might have something backwards. Check my logic, and try it on your situation, and see if it helps in your application or not.