#15600: Exact computations in QQbar spend unreasonable amounts of time in
do_polred
---------------------------+----------------------------
Reporter: mmezzarobba | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.1
Component: performance | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
---------------------------+----------------------------
Zero-tests in `QQbar` and `AA` are very slow—slower than can be reasonably
expected of exact computations with algebraic numbers IMHO.
On some examples, it turns out that 80% or more of the time is spent
calling PARI's `polredbest`. The current implementation apparently calls
`polredbest` each time exact computations in a new extension are required,
which can be pretty expensive. It does so in the hope of finding a "nice"
primitive element whose use will speed up subsequent computations (and
perhaps also make the descriptions of the elements slightly more
readable?), but otherwise my understanding is that this step is completely
optional.
Let's try to disable it except for small degrees (the value of `max_deg`
was chosen to avoid changing the output of the tests in `qqbar.py`):
{{{
#!diff
--- a/src/sage/rings/qqbar.py
+++ b/src/sage/rings/qqbar.py
@@ -1510,7 +1510,7 @@ def clear_denominators(poly):
poly = poly(poly.parent().gen() / change)
return change, poly
-def do_polred(poly):
+def do_polred(poly, max_deg=8):
r"""
Find a polynomial of reasonably small discriminant that generates
the same number field as ``poly``, using the PARI ``polredbest``
@@ -1554,9 +1554,12 @@ def do_polred(poly):
sage: do_polred(x^4 - 4294967296*x^2 + 54265257667816538374400)
(1/4*x, 4*x, x^4 - 268435456*x^2 + 211973662764908353025)
"""
+ parent = poly.parent()
+ if poly.degree() > max_deg:
+ return parent.gen(), parent.gen(), poly
+
new_poly, elt_back = poly._pari_().polredbest(flag=1)
- parent = poly.parent()
elt_fwd = elt_back.modreverse()
return parent(elt_fwd.lift()), parent(elt_back.lift()),
parent(new_poly)
}}}
Before (`master` as of a few days ago):
{{{
sage -t --long src/sage/rings/qqbar.py
[1355 tests, 34.81 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 35.2 seconds
cpu time: 34.8 seconds
cumulative wall time: 34.8 seconds
}}}
After:
{{{
sage -t --long src/sage/rings/qqbar.py
[1355 tests, 6.09 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 6.4 seconds
cpu time: 6.1 seconds
cumulative wall time: 6.1 seconds
}}}
Now these examples may not be representative of anything, and the above
patch is a very naive solution. But it should certainly be possible to
come up with a better strategy than calling `polredbest` every time!
--
Ticket URL: <http://trac.sagemath.org/ticket/15600>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
