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)
Change History (14)
comment:1 Changed 8 years ago by
- Cc mjo added
comment:2 Changed 8 years ago by
- Status changed from new to needs_review
comment:3 Changed 8 years ago by
- 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
- Status changed from needs_work to needs_review
comment:5 Changed 8 years ago by
- 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
A few comments from Review Days:
- 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.
- 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.
- 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
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
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
- 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
comment:10 Changed 8 years ago by
- 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
- Status changed from needs_review to positive_review
thank you Michael for the good work!
Paul
comment:12 Changed 8 years ago by
- Milestone changed from sage-5.0 to sage-5.1
comment:13 Changed 8 years ago by
- Merged in set to sage-5.1.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
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).