Opened 10 years ago

Closed 3 years ago

probabilistic hermite_form recurses instead of loops

Reported by: Owned by: vbraun jason, was major sage-duplicate/invalid/wontfix linear algebra cpernet, was, rbeezer, burcin N/A

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.

Changed 10 years ago by vbraun

Example matrix exhibiting the problem

comment:1 Changed 10 years ago by vbraun

• Cc cbernet was rbeezer added

comment:2 Changed 9 years ago by burcin

• Cc cpernet burcin added; cbernet removed

comment:3 Changed 8 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 6 years ago by kartikv

• 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 embray

• 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.

Note: See TracTickets for help on using tickets.