#8558: [with patch, needs work] add a fast gcd algorithm for univariate
polynomials over absolute number fields
---------------------------+------------------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-4.4
Component: algebra | Keywords: gcd, pari, ntl, number field
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------+------------------------------------------------
Changes (by lftabera):
* keywords: gcd, pari, number field => gcd, pari, ntl, number field
Comment:
The pari algorithm is not fast enough. I have implemented a modular
algorithm using ntl.
The patch needs doctest and integration in sage (it is, right now, a
separate function).
It adds a new function modular_gcd
To test it, apply the patch and
from sage.rings.polynomial.polynomial_absolute_number_field import
modular_gcd
Some timmings: (800 Mhz i386 linux, 1Gb ram)
{{{
sage: N.<a>=NumberField(x^3 -123)
sage: K.<t>=N[]
sage: f=K.random_element(degree=2)
sage: g1=K.random_element(degree=15)
sage: g2=K.random_element(degree=15)
sage: h1=f*g1
sage: h2=f*g2
sage: %time modular_gcd(h1,h2,'pari')
CPU times: user 0.30 s, sys: 0.00 s, total: 0.30 s
Wall time: 0.31 s
t^2 + (-35396/663609*a^2 + 92498/663609*a + 1750733/663609)*t -
1312/663609*a^2 + 3026/221203*a + 66060/221203
sage: %time modular_gcd(h1,h2)
CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s
Wall time: 0.12 s
t^2 + (-35396/663609*a^2 + 92498/663609*a + 1750733/663609)*t -
1312/663609*a^2 + 3026/221203*a + 66060/221203
sage: %time modular_gcd(h1,h2,'euclidean')
CPU times: user 11.28 s, sys: 0.05 s, total: 11.33 s
Wall time: 12.21 s
t^2 + (-35396/663609*a^2 + 92498/663609*a + 1750733/663609)*t -
1312/663609*a^2 + 3026/221203*a + 66060/221203
}}}
{{{
sage: N.<a>=NumberField(x^10 - 123)
sage: K.<t>=N[]
sage: f=K.random_element(degree=2)
sage: g1=K.random_element(degree=15)
sage: g2=K.random_element(degree=15)
sage: h1=f*g1
sage: h2=f*g2
sage: %time l=modular_gcd(h1,h2,'pari')
CPU times: user 30.06 s, sys: 0.02 s, total: 30.07 s
Wall time: 32.15 s
sage: %time l=modular_gcd(h1,h2,'modular')
CPU times: user 0.43 s, sys: 0.00 s, total: 0.43 s
Wall time: 0.47 s
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8558#comment:2>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
