#8558: add a fast gcd algorithm for univariate polynomials over absolute number
fields
-------------------------------------+-------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: needs_work
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 am not a pari developer, it would certainly benefit more people than an
implementation in Sage. I thought about an implementation in ntl, but I do
not touch C++ since 15 years ago. Flint would also be a good place to put
a similar code.
According to the documentation:
gcd uses:
* integers: use modified right-shift binary ("plus-minus" variant).
* univariate polynomials with coefficients in the same number field (in
particular rational): use modular gcd algorithm.
* general polynomials: use the subresultant algorithm if coefficient
explosion is likely (non modular coefficients).
So, it may be the case that we are not translating polynomials to the
correct pari setting and so I get bad timings? It may be the case, in
order not to compute the discriminant of the number field we are dealing
with...
--
Ticket URL: <https://trac.sagemath.org/ticket/8558#comment:56>
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.
