GCD for univariate polynomials over fraction fields

[sagetrac-mfrancis]

Some of the sagemath packages we use requires us to compute the GCD of univariate polynomials whose coefficient ring is the fraction field of multivariate polynomials over integral domains like Z, e.g: polynomials in the ring Frac(Z[x,y])[z].

Right now in Sagemath if we run the following example, the regular Euclidean algorithm implemented in rings.py for computing gcd is called. It is very slow and the implementation hangs for degrees >4.

Example :

sage: A.<x,y>=ZZ[]

sage: B= Frac(A)

sage: C. = B[]

sage: p = C.random_element(6)

sage: q = C.random_element(6)

sage: gcd(p,q)

Hangs!

Reason for the function to hang : It repeatedly has to call the multiplication function which calls the gcd function in multi_polynomial_libsingular.pyx and therefore is slow.

Proposed Change: Add a new function _gcd_univariate_polynomial() inside the class, class FractionField_generic(ring.Field). It can be found in /src/sage/rings/fraction_field.py.

Depends on #25233

CC: @mezzarobba

Component: algebra

Keywords: gcd, univariate polynomials, fraction fields as coefficients

Author: Maria Francis, Marc Mezzarobba

Branch/Commit: 2bf9251

Reviewer: Bruno Grenet

Issue created by migration from https://trac.sagemath.org/ticket/23909

[sagetrac-git]

Commit: bde90c8

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

bde90c8

Added gcd for univariate case over fraction field

[sagetrac-msaaltink]

comment:3

This change breaks many gcd computations that now work. For example

sage: Q.<x> = B[]
sage: F = Q.fraction_field()
sage: R.<y> = F[]
sage: f = (y + x)^2 * (y - 1/x)^3
sage: g = (y + x)^4 * (y - 1/x)^2
sage: gcd(f,g)

When B is ZZ or Zmod(5) or GaussianIntegers(), we get answers in Sage as it is. With your change, all of them raise a TypeError on some internal gcd call.

Moreover, the result of gcd should be in the same ring as the arguments. We do not always get that with this change.

[sagetrac-mfrancis]

Changed branch from u/mfrancis/fraction_field_univariate to u/mfrancis/fraction_field_univariatepoly

[sagetrac-mfrancis]

Changed commit from bde90c8 to 1757afb

[sagetrac-mfrancis]

comment:5

Made the changes : 1. Corrected it for Z, finite fields ( fields defined as Z mod p call the previous implementation, the usual Euclidean algorithm), and the returned gcd is the same ring as the input polynomials.

---

New commits:

1757afb

Made the changes to accomodate finite fields.

[jdemeyer]

comment:7

The documentation is badly misformatted. See http://doc.sagemath.org/html/en/developer/coding_basics.html#documentation-strings

And this is completely unreadable:

if (is_IntegerRing(f.base_ring().base_ring()) == True or is_IntegerRing(g.base_ring().base_ring())== True or (f.base_ring().base_ring().is_field() == True and (is_IntegerModRing(f.base_ring().base_ring()) == False or is_FiniteField(f.base_ring().base_ring()) == True)) or (g.base_ring().base_ring().is_field() == True and (is_IntegerModRing(g.base_ring().base_ring()) == False or is_FiniteField(g.base_ring().base_ring()) == True)) ) :

[mezzarobba]

Changed author from MARIA FRANCIS to Maria Francis, Marc Mezzarobba

[mezzarobba]

comment:8

Hi Maria,

As it turns out, most of the necessary work had already been done in the implementation of gcd() for polynomials over polynomial rings. Here is a simpler implementation that takes advantage of that.

(Sorry that it took me so incredibly long to have a stab at this as promised!)

---

New commits:

86d30f8

speed up gcd() of polynomials over fraction fields

[mezzarobba]

Changed commit from 1757afb to 86d30f8

[mezzarobba]

Changed branch from u/mfrancis/fraction_field_univariatepoly to u/mmezzarobba/23909-gcd_over_fraction_fields

[mezzarobba]

comment:9

Note: this does break

sage: Pol = Frac(QQ['x'])['x']
sage: p = Frac(QQ['x'])['x'].one()
sage: p.gcd(p)
...
ValueError: variable name 'x' appears more than once

because the same thing with polynomials over a polynomial ring is already broken, see #25233. I think this is an acceptable regression, at least temporarily... Edit: fixed at #25233!

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4ac14cc	Support repeated variable names in FlatteningMorphism
e26d75a	cached flattening_morphism() method for univariate polynomial rings
54a8262	use FlatteningMorphism in gcd over stacked polynomial rings
fdb3a93	speed up gcd() of polynomials over fraction fields

[sagetrac-git]

Changed commit from 86d30f8 to fdb3a93

[mezzarobba]

Dependencies: #25233

[sagetrac-git]

Changed commit from fdb3a93 to e347c74

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

26a3ed1	use FlatteningMorphism in gcd over stacked polynomial rings
e347c74	speed up gcd() of polynomials over fraction fields

[sagetrac-git]

Changed commit from e347c74 to ad86b39

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ad86b39

fix gcd(0,0) for polynomials over fraction fields

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

0d56c5f	Support repeated variable names in FlatteningMorphism
751fe89	cached flattening_morphism() method for univariate polynomial rings
8de9bbf	use FlatteningMorphism in gcd over stacked polynomial rings
1379f64	speed up gcd() of polynomials over fraction fields
69ca4c1	fix gcd(0,0) for polynomials over fraction fields

[sagetrac-git]

Changed commit from ad86b39 to 69ca4c1

[mezzarobba]

comment:17

See also #25318 for an additional improvement.

[mezzarobba]

comment:18

As far as I can tell, the last two patchbot failures are not related to this ticket—i.e. the tests still pass with sage-8.3.beta3.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

68fc7a1	speed up gcd() of polynomials over fraction fields
b2599f4	fix gcd(0,0) for polynomials over fraction fields

[sagetrac-git]

Changed commit from 69ca4c1 to b2599f4

[bgrenet]

comment:20

Looks good to me, except the docstring. Could you add a short description?

[sagetrac-git]

Changed commit from b2599f4 to 2bf9251

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2bf9251

#23909 improve docstring

[mezzarobba]

comment:22

Replying to @bgrenet:

Looks good to me, except the docstring. Could you add a short description?

Done, thanks for your commment!

[vbraun]

comment:24

Reviewer name is missing

[mezzarobba]

Reviewer: Bruno Grenet

[vbraun]

Changed branch from u/mmezzarobba/23909-gcd_over_fraction_fields to 2bf9251