id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
21579,Errors calculating characteristic polynomials of rational matrices,bober,,"I'm leaving the description below because that's where I first ran into problems, but this seems like a much more basic issue. I suspect some sort of memory bug, because I'm getting different results based on the order in which I execute functions.
This could just be a problem with polynomials. I haven't quite diagnosed it yet.
{{{#!python
A = Matrix([[ 10/7, 3/4, 1, 8/7, 3, -1/7, -1, -1, 7/4, -2, 3, 1/2, -8/3, 3/8, -10/7, -3, -1/2, -4/7, 9/8, -4],
[ 3/2, 3/5, -3/10, -4/3, -2/7, -3/2, -1, 3, 2, 0, 4/3, -2, 4/9, -1/2, -1/5, 1, 7/8, 1, -5/2, 10/9],
[ 9/10, 7, 3, 0, -3/2, 1/3, -5, 8/3, 6/7, 0, 7/4, -4/3, -1/2, -1/6, -1/4, -3/7, -6/5, -1/9, -1/3, -8/5],
[ 8, 1/2, -8/7, 1, -3/8, -7, -10/7, 1, 4/3, 0, 0, 4, -3, -1/4, 5, -1, -1, 0, -2/7, -10/3],
[ 8/3, 5, -2/3, 9/4, -9/8, -1/3, -2/3, -1, -8, 4/3, -3/4, -5/4, -2/3, -1/2, 5, -1/3, 10, 1/2, -5/3, 9/2],
[-10/9, -3, -7, 1/2, 5/9, 0, 3, -1, 9/4, -3/8, -10, 0, 6, -1/6, -2, -9/8, 2/3, 6, 0, 0],
[ -2/5, 6/5, 0, 0, -6/7, -9/10, -2/7, -1/10, -1/3, 7/2, 1/3, -3/2, 7/2, 3/2, 1/3, 0, 7/2, -2/9, 2/3, -1/8],
[ 1/3, 3, 10/3, 1, -1/2, -3/8, -5, 3/2, 1/3, 0, -1/2, 4/9, -7/5, 0, -3/2, 9/10, -1, 1/2, -1, -9/10],
[ -1, 3/8, 1, -2/5, 1/3, 1, -3/2, -4, -1, -4, 1, 1, -9/10, 0, 1, -1, -7/6, 0, -10/9, 0],
[ -6, 0, -8/5, -9/7, 7, -1/3, -8/9, -8, 7/9, 1/2, 1, -1, 1, -2/7, 8/3, -1/3, -4/5, 2/3, -5, -1/7],
[ 5/3, 1/3, -9/7, -2, 4/5, -5/7, 1/4, -5/8, -1, 5/7, 3/2, -3/2, 2/5, 0, -1/2, 1/4, 0, 3, 1, 0],
[ -7/8, -1, 6, -9/7, 3/5, 1/2, 2, 7/2, 1, -6, -7/2, 1/9, -1, -7/5, -5, -5, -2/7, -5/4, -3, -3],
[ -7/3, 1/5, -2, -8, 1/2, 2, 0, 2/7, -1/4, 0, 0, -4/7, 1/3, -1, -5, 3/2, 10, 3/10, 1/3, 3/4],
[ 8/5, 0, -4/5, 0, 1/4, -8/5, -4/9, 5, -7/9, 1/9, -7/8, -5/8, -1/4, 10, -1, -8/9, 1/2, 1/6, -8/7, 1/7],
[ -2/5, -5/4, 2, 1/2, -3/5, -5/4, -10/9, 1/2, 3/5, 9/7, -5/6, -3/7, 7/6, -4/5, -9/5, -7/3, -1/3, 1, 5, -2/5],
[ -1/2, 2, 0, 3, 5/6, 0, -3, -1/3, 1/2, 1, 2/9, -5/7, -1, -8, 1/2, 10, -5, 1/2, 1, 5],
[ 8/3, -2, -2, -4/3, 9/2, -4/5, 10/7, -1/2, 9, -1/3, -10/7, -4, 7, -1/10, 10/9, -7/6, 2/7, 2/7, 0, 8],
[ -2/3, 1/2, 4, -3/5, -2/3, -2/7, 9/10, -1/4, -5/3, 6, -1/3, -1, -5/4, -4/3, -6, -8/7, -2, 1, 5/6, 1/3],
[-10/3, 5, 0, 2/5, -4/3, -1/2, -1/2, -9/4, 6, 1/5, -1/9, -2, -6/5, -2, 4, -3/4, -1, 1/4, -3/8, 1/2],
[ -7/6, -7/10, 0, 1/5, 3/4, -3/5, -2, -3/2, -1, 6/7, -5/7, 0, 9/5, -1/2, -1, -2, -7, 0, -4/5, -9/2]])
k = int(sys.argv[1])
if k == 0:
sage.matrix.matrix_integer_dense.USE_LINBOX_POLY = True # True is the default
A._clear_cache()
f = A.charpoly() # should be using linbox
sage.matrix.matrix_integer_dense.USE_LINBOX_POLY = False # Setting this False should force
# integer charpoly to use flint when
# algorithm=='linbox'. (Rational
# matrices don't have a flint option.)
A._clear_cache()
g = A.charpoly() # should use flint, I think
A._clear_cache()
h = A.charpoly(algorithm='generic')
elif k == 1:
sage.matrix.matrix_integer_dense.USE_LINBOX_POLY = False
A._clear_cache()
g = A.charpoly() # should use flint, I think
sage.matrix.matrix_integer_dense.USE_LINBOX_POLY = True
A._clear_cache()
f = A.charpoly() # should be using linbox
A._clear_cache()
h = A.charpoly(algorithm='generic')
if k == 0 or k == 1:
print 'flint == linbox:', f == g
print 'flint == generic:', g == h
print 'linbox == generic:', f == h
print 'linbox (maybe) correct? ', f(A) == 0
print 'flint (maybe) correct?', g(A) == 0
print 'generic (maybe) correct?', h(A) == 0
sage.matrix.matrix_integer_dense.USE_LINBOX_POLY = True
if k in [0,1,2]:
# let's try computing the charpoly the way that
# B.charpoly() does it to see what goes wrong.
B, denom = A._clear_denom()
B._clear_cache()
f1 = B.charpoly(algorithm='linbox')
B._clear_cache()
g1 = B.charpoly(algorithm='flint')
print 'flint == linbox', f1 == g1
print 'linbox (maybe) correct?', f1(B) == 0
print 'flint (maybe) correct?', g1(B) == 0
x = f1.parent().gen()
F = f1(x * denom) * (1 / (denom**f1.degree()))
x = g1.parent().gen()
G = g1(x * denom) * (1 / (denom**g1.degree()))
print 'flint == linbox', F == G
if x == 0 or x == 1:
print 'linbox == linbox', f == F
print 'flint == flint?', g == G
print '2nd linbox (maybe) correct?', F(A) == 0
print '2nd flint (maybe) correct?', G(A) == 0
if k == 3:
# let's try computing the charpoly the way that
# B.charpoly() does it to see what goes wrong.
B, denom = A._clear_denom()
f1 = B.charpoly(algorithm='linbox')
print 'linbox (maybe) correct?', f1(B) == 0
x = f1.parent().gen()
F = f1(x * denom) * (1 / (denom**f1.degree()))
print '2nd linbox (maybe) correct?', F(A) == 0
if k == 4:
# let's try computing the charpoly the way that
# B.charpoly() does it to see what goes wrong.
B, denom = A._clear_denom()
g1 = B.charpoly(algorithm='flint')
print 'flint (maybe) correct?', g1(B) == 0
x = g1.parent().gen()
G = g1(x * denom) * (1 / (denom**g1.degree()))
print '2nd flint (maybe) correct?', G(A) == 0
}}}
On the most recent version of the develop branch, here's output that I get consistently:
{{{
jb12407@lmfdb5:~/sage-bug$ sage bug.sage 0
flint == linbox: False
flint == generic: False
linbox == generic: True
linbox (maybe) correct? True
flint (maybe) correct? False
generic (maybe) correct? True
flint == linbox True
linbox (maybe) correct? True
flint (maybe) correct? True
flint == linbox True
2nd linbox (maybe) correct? False
2nd flint (maybe) correct? False
jb12407@lmfdb5:~/sage-bug$ sage bug.sage 1
flint == linbox: True
flint == generic: False
linbox == generic: False
linbox (maybe) correct? False
flint (maybe) correct? False
generic (maybe) correct? True
flint == linbox True
linbox (maybe) correct? True
flint (maybe) correct? True
flint == linbox True
2nd linbox (maybe) correct? False
2nd flint (maybe) correct? False
jb12407@lmfdb5:~/sage-bug$ sage bug.sage 2
flint == linbox True
linbox (maybe) correct? True
flint (maybe) correct? True
flint == linbox True
2nd linbox (maybe) correct? False
2nd flint (maybe) correct? False
jb12407@lmfdb5:~/sage-bug$ sage bug.sage 3
linbox (maybe) correct? True
2nd linbox (maybe) correct? True
jb12407@lmfdb5:~/sage-bug$ sage bug.sage 4
flint (maybe) correct? True
2nd flint (maybe) correct? False
}}}
All those `False`s ought to be `True`. Option 3 does get the right answer, but I was getting (less directly repeatable) bugs just by calling charpoly() repeatedly on the same (rational) matrix, which should have been using only linbox.
In another (nonrepeated, interactive) test, I wound up in a situation that was something like
{{{
sage: f = A.charpoly(algorithm='flint')
sage: g = A.charpoly(algorithm='linbox')
sage: f == g
True
sage: f(A) == 0
True
sage: g(A) == 0
False
sage: print f
...
sage: print g
...
# yes, the certainly looked the same!
}}}
(I might have the True and False mixed up, though.)
---
Old Description:
I ran the following code for a bit
{{{#!python
@parallel
def test(n):
M = ModularSymbols(3633, 2, -1)
S = M.cuspidal_subspace().new_subspace()
f = S.hecke_matrix(2).characteristic_polynomial()
return S.dimension(), f
for result in test(range(5000)):
print result
}}}
and line 530 of the output is `(((15,), {}), (171, 1))`.
line 621 is `(((22,), {}), (171, 1))`
line 663 is `(((156,), {}), (171, 1))`
Line 757 starts `(((281,), {}), (171, 2167647436431476168725215705905073292546268...` and has a bit over 14 million characters. I haven't checked the degree of the polynomial yet.
(Most lines look something like `(((28,), {}), (171, x^171 - x^170 ...` and have a bit less than 6800 characters.)
That's a random but pretty high failure rate, and also suggests that when whatever might go wrong does go wrong, the computation takes a lot longer to run than normal.
I may follow up with more tests. I have no idea what is going wrong or if there is something special about the level. I only tried level 3633 because in a separate computation I saw an error there which I was trying to reproduce. In that case I was actually getting a degree 170 polynomial somehow (and I did not separately record the reported dimension of the space), so I may leave this running for a while to see if that ever happens.",defect,closed,major,sage-duplicate/invalid/wontfix,linear algebra,wontfix,,cpernet,,,,N/A,,u/cpernet/errors_calculating_characteristic_polynomials_of_rational_matrices,08012ea976866316645c2c63cf834d5317a50301,#24214,