Test timeout in FFPACK::CharPoly

[vbraun]

There are occasional timeouts on the buildbot that point to FFPACK::CharPoly. Possibly a linbox bug? Sample traces in the comments.

[vbraun]

sage -t --long src/sage/graphs/graph_generators.py
    Timed out
[...]
sage: g=graphs.cospectral_graphs(6, matrix_function=lambda g: g.laplacian_matrix()) ## line 967 ##
------------------------------------------------------------------------
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/cysignals/signals.so(+0x44a8)[0xf6b3f4a8]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/cysignals/signals.so(+0x451f)[0xf6b3f51f]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/cysignals/signals.so(+0x69f7)[0xf6b419f7]
[0xf77a0cb0]
/home/buildbot/slave/sage_git/build/local/lib/libffpack.so.1(_ZN6FFPACK17CharpolyArithProgIN6Givaro7ModularIddEESt6vectorIdSaIdEEEERSt4listIT0_SaIS8_EERKT_SB_jNSC_11Element_ptrEjj+0x31e)[0xd120863e]
/home/buildbot/slave/sage_git/build/local/lib/libffpack.so.1(_ZN6FFPACK8CharPolyIN6Givaro7ModularIddEESt6vectorIdSaIdEEEERSt4listIT0_SaIS8_EERKT_SB_jNSC_11Element_ptrEjNS_19FFPACK_CHARPOLY_TAGE+0x269)[0xd1208039]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(_ZNK6LinBox16BlasMatrixDomainIN6Givaro7ModularIddEEE8charpolyINS_10BlasVectorIS3_St6vectorIdSaIdEEEENS_10BlasMatrixIS3_S9_EEEERT_SE_RKT0_+0xc0)[0xd0f099b0]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(_ZN6LinBox19ChineseRemainderSeqINS_14EarlyMultipCRAIN6Givaro7ModularIddEEEEEclINS2_9givvectorINS2_7IntegerESaIS9_EEENS_22IntegerModularCharpolyINS_10BlasMatrixINS2_5ZRingIS9_EESt6vectorIS9_SA_EEENS_21BlasEliminationTraitsEEENS_19RandomPrimeIteratorEEERT_SN_RT0_RT1_+0x2d3)[0xd0f13cb3]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(_ZN6LinBox8charpolyIN6Givaro9givvectorINS1_7IntegerESaIS3_EEENS_10BlasMatrixINS1_5ZRingIS3_EESt6vectorIS3_S4_EEEEERT_SD_RKT0_RKNS_14RingCategories10IntegerTagERKNS_21BlasEliminationTraitsE+0x235)[0xd0f14225]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(_ZN6LinBox8charpolyINS_10BlasMatrixIN6Givaro5ZRingINS2_7IntegerEEESt6vectorIS4_SaIS4_EEEENS2_9givvectorIS4_S7_EEEERT0_SD_RKT_+0x9f)[0xd0f1450f]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(+0x22c2a)[0xd0ef5c2a]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense.so(+0x3672b)[0xd14ed72b]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense.so(+0x37e32)[0xd14eee32]
/home/buildbot/slave/sage_git/build/local/lib/libpython2.7.so.1.0(PyCFunction_Call+0x109)[0xf7639429]

[vbraun]

sage -t --long src/sage/modular/hecke/submodule.py
    Timed out
[...]
sage: M.eisenstein_submodule().hecke_bound() ## line 984 ##
------------------------------------------------------------------------
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/cysignals/signals.so(+0x5e15)[0x7f927bf45e15]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/cysignals/signals.so(+0x5e65)[0x7f927bf45e65]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/cysignals/signals.so(+0x84d1)[0x7f927bf484d1]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x10330)[0x7f9280f31330]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(_ZNK6Givaro7ModularIddE6isZeroERKd+0xe)[0x7f8c6fd2c59e]
/home/buildbot/slave/sage_git/build/local/lib/libffpack.so.1(_ZN6FFPACK17CharpolyArithProgIN6Givaro7ModularIddEESt6vectorIdSaIdEEEERSt4listIT0_SaIS8_EERKT_SB_mNSC_11Element_ptrEmm+0x245)[0x7f8c71284985]
/home/buildbot/slave/sage_git/build/local/lib/libffpack.so.1(_ZN6FFPACK8CharPolyIN6Givaro7ModularIddEESt6vectorIdSaIdEEEERSt4listIT0_SaIS8_EERKT_SB_mNSC_11Element_ptrEmNS_19FFPACK_CHARPOLY_TAGE+0xcf)[0x7f8c7128437f]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(_ZNK6LinBox16BlasMatrixDomainIN6Givaro7ModularIddEEE8charpolyINS_10BlasVectorIS3_St6vectorIdSaIdEEEENS_10BlasMatrixIS3_S9_EEEERT_SE_RKT0_+0xaa)[0x7f8c6fd3ccda]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(_ZN6LinBox19ChineseRemainderSeqINS_14EarlyMultipCRAIN6Givaro7ModularIddEEEEEclINS2_9givvectorINS2_7IntegerESaIS9_EEENS_22IntegerModularCharpolyINS_10BlasMatrixINS2_5ZRingIS9_EESt6vectorIS9_SA_EEENS_21BlasEliminationTraitsEEENS_19RandomPrimeIteratorEEERT_SN_RT0_RT1_+0x2c1)[0x7f8c6fd466e1]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(_ZN6LinBox8charpolyIN6Givaro9givvectorINS1_7IntegerESaIS3_EEENS_10BlasMatrixINS1_5ZRingIS3_EESt6vectorIS3_S4_EEEEERT_SD_RKT0_RKNS_14RingCategories10IntegerTagERKNS_21BlasEliminationTraitsE+0x1f5)[0x7f8c6fd46bb5]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(_ZN6LinBox8charpolyINS_10BlasMatrixIN6Givaro5ZRingINS2_7IntegerEEESt6vectorIS4_SaIS4_EEEENS2_9givvectorIS4_S7_EEEERT0_SD_RKT_+0x8f)[0x7f8c6fd46eaf]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/libs/linbox/linbox_flint_interface.so(+0x2bcca)[0x7f8c6fd2bcca]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense.so(+0x2ad3e)[0x7f8c72765d3e]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense.so(+0x2c1d0)[0x7f8c727671d0]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/matrix/matrix_rational_dense.so(+0x23134)[0x7f8c720b4134]
/home/buildbot/slave/sage_git/build/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x8bda)[0x7f928124e11a]
/home/buildbot/slave/sage_git/build/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x80d)[0x7f928124ec2d]
/home/buildbot/slave/sage_git/build/local/lib/libpython2.7.so.1.0(+0x865a5)[0x7f92811c55a5]

[vbraun]

To reproduce run the matchpoly.pyx doctest in a loop:

for i in `seq 0 1000` ; do sage -t --long src/sage/graphs/matchpoly.pyx ; done

Usually takes about 4s, but empirically hangs in about 1% of the runs.

[jdemeyer]

Could be related to #15535.

[klee]

Replying to jdemeyer:

Could be related to #15535.

Then a solution of #21579 would solve the issue of the present ticket.

[bober]

Replying to klee:

Replying to jdemeyer:

Could be related to #15535.

This might be the same as the problem at #15535, but I haven't seen the "running out of primes" message, but maybe that's a change in linbox that didn't actually fix the problem. Clement's email to sage-devel referenced at the end of #15535 might describe how to fix the problem, though.

Then a solution of #21579 would solve the issue of the present ticket.

#21579 is a different problem, or it turned out to be 2 problems. We have a patch to fix the infinite loop, I guess, but linbox still gives me wrong answers sometimes.

I guess we should apply the linbox patch until there is a new version of linbox, but possibly also change flint to be the default.

[cpernet]

Hi, I suspect this may be due to the unlikely corner case where we sample at random the zero vector to be used as a Krylov iterate. I forced this vector sto be zero and noticed that charpoly indeed hangs forever. I pushed a patch in this ticket's branch which forces to sample a non-zero vector. I could not reproduce the bug in the first place, so any feedback whether this patch fixes the problem would be welcome.

---

New commits:

​976f94d

patch probably fixing 23391

[cpernet]

Apologies: this patch works against upstream but not v2.2.2 shipped in sage presently. I'm preparing another patch. Sorry for the noise.

[cpernet]

Finally some news:

• I could reproduce the hang with the command in Volker's comment 5
• Running the same test on the branch u/cpernet/errors_calculating_characteristic_polynomials_of_rational_matrices of #21579 seems to fix this bug
• Running the same test on upsteam develop branch with the patches of #21579 applied seems to fix the bug too.

Should be call this a duplicate of #21579 ? Or move the patches of #21579 to a branch here, and let #21579 open, as another bug is waiting for a fix there ?

[mderickx]

I just came here because of a patchbot failure on ​multscher

Replying to cpernet:

Or move the patches of #21579 to a branch here, and let #21579 open, as another bug is waiting for a fix there ?

I would go with this solution. In general I would advertise this strategy: Every piece of code that does something useful on its own deserves its own ticket, and in general it is a good thing to split smaller standalone tickets of from a bigger ticket. This is for several reasons (which I stole from Jeroen Demeyer):

1. Small tickets are easier to review because the reviewer only needs to look at a small set of changes.
2. Different tickets can have different sets of authors/reviewers, each with their own interests/specialities.
3. Prevents code rot by getting code into sage quicker. The useful code from the smaller split of ticket will get into sage even if the effort to solve the bigger ticket fails for some reason.

[cpernet]

#24214 should fix it.

[klee]

Replying to cpernet:

#24214 should fix it.

So it seems. Volker's test never fails on my machine.

[cpernet]

Ok, I set it as positive review as it was fixed in #24214.

[vdelecroix]

closing positively reviewed duplicates