Random failure in test-minpoly (also test-solve)

[tornaria]

Reproduced with:

$ seq 1000 | while read seed ; do ./test-minpoly -i 1 -s $seed && echo -n . || echo -n FAIL:$seed; done
...................................................................................................................................................................................................................................................................FAIL:260..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................FAIL:975.........................

However, the test is not deterministic so running the test with the failed seed won't always fail:

$ while ./test-minpoly -i 1 -s 260 ; do echo -n . ; done ; echo FAIL
.......................................................................FAIL
$ while ./test-minpoly -i 1 -s 260 ; do echo -n . ; done ; echo FAIL
...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................FAIL

The nonzero entires of the random sparse matrices seem to be always the same, but the positions of those change.

Something like this:

--- a/tests/test-minpoly.C
+++ b/tests/test-minpoly.C
@@ -384,7 +384,7 @@ bool run_with_field(integer q, int e, uint64_t b, size_t n, int iter, int numVec
         typedef typename SparseMatrix<Field>::Row SparseVector;
         typedef DenseVector<Field> DenseVector;
         RandomDenseStream<Field, DenseVector, typename Field::NonZeroRandIter> zv_stream (*F, NzG, n, numVectors);
-        RandomSparseStream<Field, SparseVector, typename Field::NonZeroRandIter > zA_stream (*F, NzG, (double) k / (double) n, n, n);
+        RandomSparseStream<Field, SparseVector, typename Field::NonZeroRandIter > zA_stream (*F, NzG, (double) k / (double) n, n, n, seed);
 
         ok &= testRandomMinpoly    (*F, iter, zA_stream, zv_stream, Method::Auto());
         ok &= testRandomMinpoly    (*F, iter, zA_stream, zv_stream, Method::Elimination());

seems to make the matrices deterministic, but the actual minpoly() call seems to still be nondeterministic... I tried running srand(seed) without success...

This was detected by a CI run in void-linux/void-packages#43659. Another run gave a test failure for test-solve but I haven't run the second one locally since tests not being deterministic completely discouraged me from further investigation.

IIRC from looking at logs, one failure was a matrix with charpoly = minpoly of degree 30 and divisible by x^2 but sometimes minpoly() would return a polynomial of degree 29 (divisible by x but not x^2). To get such logs I did something like:

$ ./test-minpoly -i 1 -s 260 report-good.log
...
$ while ./test-minpoly -i 1 -s 260  report-bad.log ; do echo -n . ; done ; echo FAIL
...

then compare both files (you will notice matrices are different unless you apply my patch above).

[jgdumas]

Solved by PR#303