#23391 closed defect (wontfix)

Test timeout in FFPACK::CharPoly

Reported by: vbraun Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/cpernet/test_timeout_in_ffpack__charpoly (Commits) Commit: 976f94db60f127934bc7166c9e1053440bf54d73
Dependencies: #24214 Stopgaps:

Description (last modified by vbraun)

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

Change History (17)

comment:1 Changed 23 months ago by 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]

comment:2 Changed 23 months ago by 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]

comment:3 Changed 23 months ago by vbraun

  • Description modified (diff)

comment:4 Changed 23 months ago by vbraun

  • Description modified (diff)

comment:5 Changed 23 months ago by 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.

comment:6 follow-up: Changed 23 months ago by jdemeyer

Could be related to #15535.

comment:7 in reply to: ↑ 6 ; follow-up: Changed 23 months ago by klee

Replying to jdemeyer:

Could be related to #15535.

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

comment:8 in reply to: ↑ 7 Changed 22 months ago by 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.

comment:9 Changed 21 months ago by cpernet

  • Branch set to u/cpernet/test_timeout_in_ffpack__charpoly

comment:10 Changed 21 months ago by cpernet

  • Commit set to 976f94db60f127934bc7166c9e1053440bf54d73

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:

976f94dpatch probably fixing 23391

comment:11 Changed 21 months ago by 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.

comment:12 follow-up: Changed 21 months ago by 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 ?

comment:13 in reply to: ↑ 12 Changed 20 months ago by 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.

comment:14 follow-up: Changed 18 months ago by cpernet

  • Dependencies set to #24214

#24214 should fix it.

comment:15 in reply to: ↑ 14 Changed 14 months ago by klee

  • Milestone changed from sage-8.0 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

Replying to cpernet:

#24214 should fix it.

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

comment:16 Changed 14 months ago by cpernet

  • Status changed from needs_review to positive_review

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

comment:17 Changed 12 months ago by vdelecroix

  • Resolution set to wontfix
  • Status changed from positive_review to closed

closing positively reviewed duplicates

Note: See TracTickets for help on using tickets.