Opened 2 years ago
Closed 17 months ago
#23391 closed defect (wontfix)
Test timeout in FFPACK::CharPoly
Reported by:  vbraun  Owned by:  

Priority:  major  Milestone:  sageduplicate/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 )
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 2 years ago by
comment:2 Changed 2 years ago by
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/sitepackages/cysignals/signals.so(+0x5e15)[0x7f927bf45e15] /home/buildbot/slave/sage_git/build/local/lib/python2.7/sitepackages/cysignals/signals.so(+0x5e65)[0x7f927bf45e65] /home/buildbot/slave/sage_git/build/local/lib/python2.7/sitepackages/cysignals/signals.so(+0x84d1)[0x7f927bf484d1] /lib/x86_64linuxgnu/libpthread.so.0(+0x10330)[0x7f9280f31330] /home/buildbot/slave/sage_git/build/local/lib/python2.7/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/sage/libs/linbox/linbox_flint_interface.so(+0x2bcca)[0x7f8c6fd2bcca] /home/buildbot/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/matrix/matrix_integer_dense.so(+0x2ad3e)[0x7f8c72765d3e] /home/buildbot/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/matrix/matrix_integer_dense.so(+0x2c1d0)[0x7f8c727671d0] /home/buildbot/slave/sage_git/build/local/lib/python2.7/sitepackages/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 2 years ago by
 Description modified (diff)
comment:4 Changed 2 years ago by
 Description modified (diff)
comment:5 Changed 2 years ago by
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 followup: ↓ 7 Changed 2 years ago by
Could be related to #15535.
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 2 years ago by
comment:8 in reply to: ↑ 7 Changed 2 years ago by
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 sagedevel 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 2 years ago by
 Branch set to u/cpernet/test_timeout_in_ffpack__charpoly
comment:10 Changed 2 years ago by
 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 nonzero 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

comment:11 Changed 2 years ago by
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 followup: ↓ 13 Changed 2 years ago by
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 2 years ago by
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):
 Small tickets are easier to review because the reviewer only needs to look at a small set of changes.
 Different tickets can have different sets of authors/reviewers, each with their own interests/specialities.
 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:15 in reply to: ↑ 14 Changed 19 months ago by
 Milestone changed from sage8.0 to sageduplicate/invalid/wontfix
 Status changed from new to needs_review
comment:16 Changed 19 months ago by
 Status changed from needs_review to positive_review
Ok, I set it as positive review as it was fixed in #24214.
comment:17 Changed 17 months ago by
 Resolution set to wontfix
 Status changed from positive_review to closed
closing positively reviewed duplicates