charpoly is recomputed when called with a different variable

[zimmerma]

When the characteristic polynomial of a given matrix is computed for two different variables, the computation is done once again:

sage: A=random_matrix(ZZ,100)
sage: time p1=A.charpoly('x')
Time: CPU 0.25 s, Wall: 0.28 s
sage: time p2=A.charpoly('x')
Time: CPU 0.00 s, Wall: 0.00 s
sage: time p3=A.charpoly('y')
Time: CPU 0.25 s, Wall: 0.29 s
sage: p1.subs(x=y) - p3
0

We see that the computation of p2 is immediate since it was cached for the variable x, but that of p3 is not, since the code searches for a cached charpoly with the variable y! It would suffice to search a cached charpoly for any variable, and substitute that variable.

[mjo]

Here's a patch that fixes the issue.

The timing doctests are of dubious value, and I'm not against removing them entirely since they aren't deterministic. They may help with review, though -- each one exercises the correct charpoly method.

Once we're sure the code is correct, they can go, or get fixed (I don't have any good ideas).

[zimmerma]

Michael,

the patch fails to apply to Sage 4.8, for which version did you make it?

----------------------------------------------------------------------
| Sage Version 4.8, Release Date: 2012-01-20                         |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
Loading Sage library. Current Mercurial branch is: 12292
sage: hg_sage.import_patch("/tmp/sag
/tmp/sage-4.8               /tmp/sage-trac_12292.patch
/tmp/sage-4.8.alpha6        
sage: hg_sage.import_patch("/tmp/sage-trac_12292.patch")
cd "/usr/local/sage-4.8/sage/devel/sage" && sage --hg import   "/tmp/sage-trac_12292.patch"
applying /tmp/sage-trac_12292.patch
patching file sage/matrix/matrix2.pyx
Hunk #4 FAILED at 1422
Hunk #5 FAILED at 1438
Hunk #6 FAILED at 1467
3 out of 6 hunks FAILED -- saving rejects to file sage/matrix/matrix2.pyx.rej
abort: patch failed to apply

Also there is a tiny typo in the patch: indepenedent should be independent (five times). Also I'm not sure about the comment:

Prior to trac #12292, the call to
A.det() would attempt to use the cached charpoly, and crash [...]

Shouldn't it be #6442 instead?

Paul

[mjo]

Sorry, forgot to mention, this applies on top of the patch at #6442.

That comment about the cached charpoly is a modification of what I said in the patch for #6442. It no longer made sense, since I got rid of the dictionary.

New patch with the typo fixed going up in a second.

[mjo]

I had based this on sage-5.0.beta1, but it applies on top of my 4.8, too, after 6442.

[rbeezer]

A few comments from Review Days:

1. For a matrix A, you can examine A._cache directly. Instead of doing timings, might it be better to check the cached value before and after the second request (the one with a new variable specified)? A return value with the new variable and a cached value with the original variable would strike me as sufficient evidence, and superior to using timings in a doctest.
2. In poking around with this it appears that the algorithm name is part of the cache key in some instances, while there are places (eg determinant computations) that just check for the "charpoly" cache key.
3. Applies on 5.0-beta8, FWIW.

sage: A = random_matrix(QQ, 3)
sage: A.charpoly()
x^3 + x^2 + 3*x - 13
sage: A._cache 
{'clear_denom': ([ 1  0 -2]
[-2 -1 -2]
[ 0  2 -1], 1), 'charpoly_linbox': x^3 + x^2 + 3*x - 13}
sage: A.charpoly('t')
t^3 + t^2 + 3*t - 13
sage: A._cache
{'clear_denom': ([ 1  0 -2]
[-2 -1 -2]
[ 0  2 -1], 1), 'charpoly_linbox': x^3 + x^2 + 3*x - 13}
sage: A._cache['charpoly_linbox']
x^3 + x^2 + 3*x - 13

[zimmerma]

I agree with item 1 from comment 6, but in Sage 4.8:

sage: A = random_matrix(QQ, 3)
sage: A.charpoly()
x^3 + x^2 + 5/4*x + 1/2
sage: A._cache 
{'clear_denom': ([-1  2  0]
[-2  0  0]
[ 0 -1 -1], 2), 'charpoly_linbox_x': x^3 + x^2 + 5/4*x + 1/2}
sage: A.charpoly('t')
t^3 + t^2 + 5/4*t + 1/2
sage: A._cache
{'clear_denom': ([-1  2  0]
[-2  0  0]
[ 0 -1 -1], 2), 'charpoly_linbox_x': x^3 + x^2 + 5/4*x + 1/2, 'charpoly_linbox_t': t^3 + t^2 + 5/4*t + 1/2}

thus calling A._cache['charpoly_linbox'] might not be enough.

Paul Zimmermann

[mjo]

I finally got around to fixing these. I just test the _cache value now; no timings. I also realized that Matrix_modn_dense is deprecated, and moved that test to the correct place in Matrix_modn_dense_template.

[zimmerma]

on top of sage-5.0.beta11, the following doctests fail:

sage -t  devel/sage-12292/sage/matrix/matrix_symbolic_dense.pyx # 5 doctests failed
sage -t  devel/sage-12292/sage/matrix/matrix2.pyx # 2 doctests failed
sage -t  devel/sage-12292/sage/matrix/matrix_modn_dense_template.pxi # 2 doctests failed

Paul

[mjo]

Fixed patch

[mjo]

I'm not sure what I did to that poor patch, those doctests would've failed with or without the new cache code. There was one real issue, though: the modn charpoly isn't unique. I'm only testing for the variable name now.

[zimmerma]

thank you Michael for the good work!

Paul