#8558: add a fast gcd algorithm for univariate polynomials over absolute number
fields
-------------------------------------+-------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: algebra | Resolution:
Keywords: gcd, pari, ntl, | Merged in:
number field |
Authors: Luis Felipe | Reviewers: Jeroen Demeyer
Tabera Alonso |
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/lftabera/ticket/8558 | eef9fe12ac4578b08fbff4b8ca5264ad5e20a8b9
Dependencies: #14186, #15803, | Stopgaps:
#15804 |
-------------------------------------+-------------------------------------
Comment (by lftabera):
- I have added mor cdef, however, I cannot do that in
polynomial_number_field since the class inherist from a python class. I
was not able to cdef, rings or number field elements. The latter has at
least two classes and I was not able to cdef the common parent.
- I have fixed types, more verbose method names, clean unusued variables.
- modular method can be further improved for high degree using half-gcd
algorithms in ntl.
- Some more examples:
Pari seems to use either Euclid or some subresultant variation. I would
expect pari to perform better when the gcd is big with respect to the
degree of the inputs. Or, when the input has small degree.
The polynomials are generated with K.random_element() so small
coefficients. This benefits pari.
Small extension, not impressing except for huge polynomials
{{{
sage: K=QQ[I]['x']
}}}
{{{
deg f, deg g, deg gcd, timeit pari, timeit modular
2, 2, 0, 111 µs, 176 µs
2, 2, 1, 173 µs, 360 µs
2, 2, 2, 185 µs, 466 µs
100, 100, 0, 30.6 ms, 7.06 ms
100, 100, 50, 22.5 ms, 34.7 ms
100, 100, 100, 4.82 ms, 6.58 ms
300, 300, 0, 1.8 s, 45.1 ms
300, 300, 150, 534 ms, 201 ms
300, 300, 300, 13.3 ms, 11.3 ms
1000, 1000, 100, 2min 52s, 2.07 s
}}}
A degree 3, easy extension
{{{
sage: R=NumberField(x^3-2,'a')['x']
}}}
{{{
deg f, deg g, deg gcd, timeit pari, timeit modular
2, 2, 0, 163 µs, 243 µs
2, 2, 1, 239 µs, 597 µs
2, 2, 2, 257 µs, 587 µs
100, 100, 0, 19 s, 11.2 ms (1000x faster)
100, 100, 50, 8.6 s, 47.3 ms (100x faster)
100, 100, 100, 6.57 ms, 11.9 ms (2x slower)
300, 300, 150, > 600 s, 403 ms
}}}
Tu support my claim that big coefficients benefits modular
{{{
sage: K=QQ[I]['x']
sage: f=K.random_element(2,10**10)
}}}
{{{
100, 100, 0, 282 ms, 6.92 ms
100, 100, 50, 117 ms, 15.4 ms
100, 100, 100, 4.69 ms, 5.01 ms
}}}
--
Ticket URL: <https://trac.sagemath.org/ticket/8558#comment:53>
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.
