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:

Status badges

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)

big_matrix.sage (453.6 KB) - added by vbraun 10 years ago.
Example matrix exhibiting the problem

Download all attachments as: .zip

Change History (9)

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.