5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Basically you are thinking of it is a polynomial identity testing problem. Here the polynomials are minors of the matrix of these vectors. The heuristic is then that the number of prime factors of the determinants shouldn't be too large. $\endgroup$ – Louis Oct 4 '15 at 11:41
  • $\begingroup$ The problem with this suggestion is that at some point, Gaussian elimination over $\mathbb{Q}$ will have to be run. While this has a quick running time, the numbers that appear in intermediate stages of this algorithm are enormous; they seem to grow exponentially in the dimension of the problem. For problems as large as I am doing, numbers requiring a bitesize of e.g. the number of particles in the universe will quickly appear. No machine has enough memory to do this, so it is entirely hopeless. I was hoping for alternate algorithms. $\endgroup$ – Andy Putman Oct 5 '15 at 1:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.