#20749: Use PARI nfeltup() for inclusion of base field into relative number
field
-------------------------------------+-------------------------------------
Reporter: pbruin | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.3
Component: number fields | Resolution:
Keywords: relative number | Merged in:
field pari | Reviewers: Stephan Ehlen
Authors: Peter Bruin | Work issues:
Report Upstream: N/A | Commit:
Branch: | 9f1d90be8d3f05b6d5de8ee75e36e6d17ad52095
u/pbruin/20749-pari_nfeltup | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ehlen):
I started to review your changes. So far I can confirm that this does what
it's supposed to do (see some timings below) but there seem to be some
negative side-effects on the creation of relative extension.
I tried the following example (which occurred when computing newforms at
some point):
{{{
sage: K.<zeta10>=CyclotomicField(10)
sage: y=polygen(K)
sage: %prun L.<a> = K.extension(y^8 + (15*zeta10^3 - 33*zeta10^2 +
33*zeta10 - 15)*y^7 + (2712*zeta10^3 + 474*zeta10 - 474)*y^6 +
(39516*zeta10^3 - 67788*zeta10^2 + 39516*zeta10)*y^5 + (-799088*zeta10^2 -
1185224*zeta10 - 799088)*y^4 + (20680992*zeta10^3 - 20680992*zeta10^2 +
11168256)*y^3 + (-432096000*zeta10^3 + 155681408*zeta10^2 -
155681408*zeta10 + 432096000)*y^2 + (1391139840*zeta10^3 -
2598142464*zeta10 + 2598142464)*y + 24488994816*zeta10^3 -
2361024512*zeta10^2 + 24488994816*zeta10)
}}}
In sage 7.1, the extension is much faster created than in this branch.
Here are the top contributions in sage 7.1:
{{{
676 function calls (670 primitive calls) in 0.056 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.049 0.049 0.049 0.049 {method '_nf_rnfeq' of
'sage.libs.pari.gen.gen' objects}
1 0.003 0.003 0.003 0.003 {method 'polisirreducible'
of 'sage.libs.pari.gen.gen' objects}
10 0.001 0.000 0.001 0.000
polynomial_ring.py:299(_element_constructor_)
5/4 0.001 0.000 0.002 0.000
number_field.py:1403(_element_constructor_)
1 0.001 0.001 0.056 0.056 <string>:1(<module>)
1 0.000 0.000 0.055 0.055
number_field_rel.py:170(__init__)
2 0.000 0.000 0.000 0.000 {method '_pari_with_name' of
'sage.rings.polynomial.polynomial_element.Polynomial' objects}
4 0.000 0.000 0.000 0.000
number_field_rel.py:1824(absolute_polynomial_ntl)
2 0.000 0.000 0.000 0.000 homset.py:542(__init__)
26 0.000 0.000 0.000 0.000
number_field.py:9271(_element_constructor_)
4 0.000 0.000 0.000 0.000 homset.py:86(Hom)
2 0.000 0.000 0.001 0.000 {method
'_generic_convert_map' of 'sage.structure.parent_old.Parent' objects}
261 0.000 0.000 0.000 0.000 {isinstance}
26 0.000 0.000 0.000 0.000
number_field.py:6684(_coerce_non_number_field_element_in)
1 0.000 0.000 0.000 0.000
number_field.py:1140(__init__)
1 0.000 0.000 0.000 0.000 {method '_first_ngens' of
'sage.structure.category_object.CategoryObject' objects}
3 0.000 0.000 0.000 0.000 {hasattr}
2 0.000 0.000 0.000 0.000
number_field_rel.py:824(_coerce_non_number_field_element_in)
1 0.000 0.000 0.049 0.049
number_field_rel.py:1845(absolute_polynomial)
2 0.000 0.000 0.000 0.000 {method '_eltreltoabs' of
'sage.libs.pari.gen.gen' objects}
}}}
And here in this branch:
{{{
694 function calls (688 primitive calls) in 0.674 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.617 0.617 0.617 0.617 {method '_nf_nfzk' of
'sage.libs.pari.gen.gen' objects}
1 0.049 0.049 0.049 0.049 {method '_nf_rnfeq' of
'sage.libs.pari.gen.gen' objects}
1 0.003 0.003 0.003 0.003 {method 'polisirreducible'
of 'sage.libs.pari.gen.gen' objects}
10 0.001 0.000 0.001 0.000
polynomial_ring.py:300(_element_constructor_)
1 0.001 0.001 0.674 0.674 <string>:1(<module>)
5/4 0.001 0.000 0.619 0.155
number_field.py:1408(_element_constructor_)
1 0.000 0.000 0.000 0.000 {method '_nfeltup' of
'sage.libs.pari.gen.gen' objects}
2 0.000 0.000 0.000 0.000 {method '_pari_with_name' of
'sage.rings.polynomial.polynomial_element.Polynomial' objects}
1 0.000 0.000 0.673 0.673
number_field_rel.py:171(__init__)
}}}
The call to {{{'_nf_nfzk'}}} is now the main contributor and creating the
extension is almost 12 times slower.
@pbruin: Do you think we can avoid slowing down the creation of extensions
somehow?
Coercing elements from the base into the extension, however, is now faster
in general (but not always).
Sage 7.1:
{{{
sage: %timeit r=L(K.gen())
1000 loops, best of 3: 503 µs per loop
sage: %timeit r=L(K.gen()^2)
10 loops, best of 3: 61.1 ms per loop
sage: %timeit
r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3)
10 loops, best of 3: 124 ms per loop
sage: %timeit
r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3+234678234782637842736426342/2374723423423874723*zeta10)
10 loops, best of 3: 126 ms per loop
}}}
This branch:
{{{
sage: %timeit r=L(K.gen())
1000 loops, best of 3: 908 µs per loop
sage: %timeit r=L(K.gen()^2)
1000 loops, best of 3: 899 µs per loop
sage: sage: %timeit
r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3)
1000 loops, best of 3: 1.03 ms per loop
sage: %timeit
r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3+234678234782637842736426342/2374723423423874723*zeta10)
}}}
In particular, the new function seems to scale much much better.
--
Ticket URL: <http://trac.sagemath.org/ticket/20749#comment:5>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
