#15790: GCD of sparse univariate polynomials over ZZ
------------------------------------+------------------------
Reporter: bruno | Owner:
Type: defect | Status: new
Priority: minor | Milestone: sage-6.0
Component: basic arithmetic | Resolution:
Keywords: GCD sparse | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
------------------------------------+------------------------
Comment (by bruno):
For `PolynomialRing(ZZ,'x',sparse=false)`, one of FLINT or NTL is used
(FLINT by default).
For `PolynomialRing(QQ,'x',sparse=true)`, the `gcd` computation is based
on `quo_rem`. This is not possible over the integer since `quo_rem` works
for polynomials over a field.
There are several possible solutions:
1. Coerce the polynomials to `PolynomialRing(QQ,'x',sparse=true)`; compute
their GCD `g`, the LCM `l` of the denominators of the coefficients of `g`,
and return `l*g`.
1. Coerce the polynomials to `PolynomialRing(ZZ,'x',sparse=false)`;
compute their GCD and return the result in sparse representation with a
second coercion.
1. Implement a //pseudo-division// algorithm (//cf.// Cohen GTM 138
Algorithm 3.1.2) and a GCD algorithm based on the sub-resultant (//cf.//
Cohen GTM 138 Algorithm 3.3.1).
Solution 3 seems cleaner but does not give especially efficient results
since the algorithms described in Cohen GTM 138 have complexity polynomial
in the degree of the input polynomial. Actually, computing the GCD of two
sparse polynomial is NP-hard ![1] so no better solution than converting to
the dense representation is likely to exist. To my mind, Solution 2 is
then the best one.
Yet, I am new to Sage so comments are welcome!
![1] D. Plaisted, Sparse complex polynomials and polynomial reducibility.
J. Comput. Syst. Sci. 14 (2), 210–221, 1977.
--
Ticket URL: <http://trac.sagemath.org/ticket/15790#comment:1>
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.
For more options, visit https://groups.google.com/groups/opt_out.
