Opened 10 years ago
Closed 3 years ago
#12359 closed defect (worksforme)
probabilistic hermite_form recurses instead of loops
Reported by: | vbraun | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | linear algebra | Keywords: | |
Cc: | cpernet, was, rbeezer, burcin | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The default hnf for integral matrices uses a heuristic choice of pivots and loops until it found working pivots. But a subroutine in the loop can call hnf again, which soon leads to RuntimeError: maximum recursion depth exceeded
. The actual loop is
File "/home/vbraun/opt/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense_hnf.py", line 1006, in hnf H, pivots = probable_hnf(A, include_zero_rows = include_zero_rows, proof=True) File "/home/vbraun/opt/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense_hnf.py", line 838, in probable_hnf H = hnf_square(C, proof=proof) File "/home/vbraun/opt/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense_hnf.py", line 574, in hnf_square x = add_column(W, H, b.stack(matrix(1,1,[k*A[m-2,m-1] + l*A[m-1,m-1]])), proof) File "/home/vbraun/opt/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense_hnf.py", line 413, in add_column return add_column_fallback(B, a, proof) File "/home/vbraun/opt/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense_hnf.py", line 292, in add_column_fallback H, _ = hnf(W, proof) File "/home/vbraun/opt/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/matrix/matrix_integer_dense_hnf.py", line 1006, in hnf H, pivots = probable_hnf(A, include_zero_rows = include_zero_rows, proof=True)
Attached is a Sage script that constructs a particular 391x391 matrix that exhibits this problem. Computing the hnf with algorithm='pari'
gives the result in seconds, but by default the echelon form crashes with the above RuntimeError
after a much longer wait.
Attachments (1)
Change History (9)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Cc cbernet was rbeezer added
comment:2 Changed 9 years ago by
- Cc cpernet burcin added; cbernet removed
comment:3 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:4 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:5 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:6 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:7 Changed 6 years ago by
- Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_info
This ticket should probably closed, as the pathway through the code taken by this example (and similar others) no longer occurs: instead, this matrix simply goes back into pari, and then hangs due to pari's choice of algorithm. Correct functionality should be mostly included in the fix to ticket #19081
comment:8 Changed 3 years ago by
- Resolution set to worksforme
- Status changed from needs_info to closed
Confirmed worksforme. In fact I'm pretty sure what caused the original bug and it's been fixed in Python as well.
Example matrix exhibiting the problem