#15790: GCD of univariate polynomials: generic implementation for UFD, and
sparse
case
-------------------------------------+-------------------------------------
Reporter: bruno | Owner:
Type: defect | Status: needs_review
Priority: minor | Milestone: sage-6.9
Component: basic arithmetic | Resolution:
Keywords: polynomial, gcd | Merged in:
Authors: Bruno Grenet | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/bruno/gcd_of_sparse_univariate_polynomials_over_zz|
f9089369482cc589372b0f3a7461d633d9540964
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by bruno):
* keywords: sparse polynomial, gcd => polynomial, gcd
* status: needs_work => needs_review
Old description:
> **[Update]** Due to #13442, the implementation of this ticket can be
> viewed as a fallback GCD implementation for rings which do not have a
> method `_gcd_univariate_polynomial`.
>
> The GCD of two sparse polynomials over `ZZ` is not computed. If the
> polynomials are in dense representation or if they are in sparse
> representation but defined over `QQ`, there is no problem.
>
> {{{
> sage: R1.<x>=PolynomialRing(ZZ,'x',sparse=true)
> sage: R2.<x>=PolynomialRing(ZZ,'x',sparse=false)
> sage: R3.<x>=PolynomialRing(QQ,'x',sparse=true)
> sage: p=x^2-3*x+2
> sage: q=x^2-1
> sage: gcd(R2(p),R2(q))
> x - 1
> sage: gcd(R3(p),R3(q))
> x - 1
> sage: gcd(R1(p),R1(q))
> ---------------------------------------------------------------------------
> TypeError Traceback (most recent call
> last)
> <ipython-input-6-0d7380207fef> in <module>()
> ----> 1 gcd(R1(p),R1(q))
>
> /home/bgrenet/bin/sage-6.0-x86_64-Linux/local/lib/python2.7/site-
> packages/sage/rings/arith.pyc in gcd(a, b, **kwargs)
> 1605 return ZZ(a).gcd(ZZ(b))
> 1606 except TypeError:
> -> 1607 raise TypeError("unable to find gcd")
> 1608 return GCD(b, **kwargs)
> 1609
>
> TypeError: unable to find gcd
> }}}
New description:
**[Update]** Due to #13442, the purpose of this ticket changed slightly.
It provides two functionalities:
1. A generic implementation for the GCD of two polynomials over a UFD;
1. A `gcd` method for sparse polynomials which allows to choose between
the `generic` implementation, or using the implementation for `dense`
polynomials. Default is generally `generic`, but for polynomial over `ZZ`
it is `dense`. This is due to the very fast implementations available in
Flint and NTL.
These implementations solve the problem mentioned in the first version of
this ticket, that remains below for information.
----
'''[Old description, not relevant anymore]'''
The GCD of two sparse polynomials over `ZZ` is not computed. If the
polynomials are in dense representation or if they are in sparse
representation but defined over `QQ`, there is no problem.
{{{
sage: R1.<x>=PolynomialRing(ZZ,'x',sparse=true)
sage: R2.<x>=PolynomialRing(ZZ,'x',sparse=false)
sage: R3.<x>=PolynomialRing(QQ,'x',sparse=true)
sage: p=x^2-3*x+2
sage: q=x^2-1
sage: gcd(R2(p),R2(q))
x - 1
sage: gcd(R3(p),R3(q))
x - 1
sage: gcd(R1(p),R1(q))
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
<ipython-input-6-0d7380207fef> in <module>()
----> 1 gcd(R1(p),R1(q))
/home/bgrenet/bin/sage-6.0-x86_64-Linux/local/lib/python2.7/site-
packages/sage/rings/arith.pyc in gcd(a, b, **kwargs)
1605 return ZZ(a).gcd(ZZ(b))
1606 except TypeError:
-> 1607 raise TypeError("unable to find gcd")
1608 return GCD(b, **kwargs)
1609
TypeError: unable to find gcd
}}}
--
Comment:
In the two latest commits, I propose the following changes:
1. Instead of having a fallback algorithm in the method `Polynomial.gcd`
which tests whether the base ring in a unique factorization domain, this
algorithm is moved to the category `UniqueFactorizationDomains`.
1. I simplified the method `Polynomial_generic_sparse.gcd`: There remain
only two possibilities (out of three), namely the one previously called
`pseudo-division` (renamed `generic`, since it uses the generic code) and
the `dense` version, which may in some cases be faster, for instance over
`ZZ`. I removed the `fraction_field` option which does not make much sense
I think.
At the same time, I also take [comment:21 Frédéric's comment] into
account.
--
Ticket URL: <http://trac.sagemath.org/ticket/15790#comment:24>
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/d/optout.
