#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-5.8
Component: algebra | Resolution:
Keywords: gcd, pari, ntl, number field | Work issues:
Report Upstream: N/A | Reviewers: Jeroen Demeyer
Authors: Luis Felipe Tabera Alonso | Merged in:
Dependencies: #14186 | Stopgaps:
------------------------------------------------+---------------------------
Old description:
> Question arised here,
>
> http://groups.google.com/group/sage-
> devel/browse_thread/thread/0f5b029970e1a4e2/fcec7d0e35474fbd#fcec7d0e35474fbd
>
> univariate gcd is performed using euclidean algorithm, which causes
> explosion of coefficients and is slow but for trivial examples. Instead
> we should use pari that performs better.
>
> 1. Make `_pari_()` work for polynomials over absolute number fields, see
> #11904.
> 2. Add gcd using pari for absolute number fields
> 3. For relative number fields, pass to an absolute representation. This
> may be slow. But for the cases where this is slow the current
> implementation may be unfeasible.
>
> Apply: [attachment:trac-8558.2.patch]
New description:
Question arised here,
http://groups.google.com/group/sage-
devel/browse_thread/thread/0f5b029970e1a4e2/fcec7d0e35474fbd#fcec7d0e35474fbd
univariate gcd is performed using euclidean algorithm, which causes
explosion of coefficients and is slow but for trivial examples. Instead we
should use pari that performs better.
1. Make `_pari_()` work for polynomials over absolute number fields, see
#11904.
2. Add gcd using pari for absolute number fields
3. For relative number fields, pass to an absolute representation. This
may be slow. But for the cases where this is slow the current
implementation may be unfeasible.
Apply: [attachment:trac-8558.2.2.patch]
--
Comment (by lftabera):
Apply: trac-8558.2.2.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8558#comment:27>
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
