#12359: probabilistic hermite_form recurses instead of loops
------------------------------+---------------------------------------------
Reporter: vbraun | Owner: jason, was
Type: defect | Status: new
Priority: major | Milestone: sage-5.0
Component: linear algebra | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
------------------------------+---------------------------------------------
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12359>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
