Opened 8 years ago

Closed 8 years ago

#12292 closed enhancement (fixed)

charpoly is recomputed when called with a different variable

Reported by: zimmerma Owned by: jason, was
Priority: minor Milestone: sage-5.1
Component: linear algebra Keywords: sd35.5
Cc: mjo Merged in: sage-5.1.beta0
Authors: Michael Orlitzky Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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.

Attachments (1)

sage-trac_12292-notimings.patch (11.0 KB) - added by mjo 8 years ago.
Fixed patch

Download all attachments as: .zip

Change History (14)

comment:1 Changed 8 years ago by mjo

  • Cc mjo added

comment:2 Changed 8 years ago by mjo

  • Authors set to Michael Orlitzky
  • Status changed from new to needs_review

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

comment:3 Changed 8 years ago by zimmerma

  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to needs_work
  • Work issues set to rebase for 4.8, fix typos

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

comment:4 Changed 8 years ago by mjo

  • Status changed from needs_work to needs_review

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.

comment:5 Changed 8 years ago by mjo

  • Work issues rebase for 4.8, fix typos deleted

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

comment:6 Changed 8 years ago by 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

comment:7 Changed 8 years ago by 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

comment:8 Changed 8 years ago by 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.

comment:9 Changed 8 years ago by zimmerma

  • Status changed from needs_review to needs_work
  • Work issues set to doctests failures

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

Changed 8 years ago by mjo

Fixed patch

comment:10 Changed 8 years ago by mjo

  • Status changed from needs_work to needs_review
  • Work issues doctests failures deleted

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.

comment:11 Changed 8 years ago by zimmerma

  • Status changed from needs_review to positive_review

thank you Michael for the good work!

Paul

comment:12 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.0 to sage-5.1

comment:13 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.1.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.