Opened 4 years ago

Closed 3 years ago

# GCD for univariate polynomials over fraction fields

Reported by: Owned by: mfrancis minor sage-8.1 algebra gcd, univariate polynomials, fraction fields as coefficients mmezzarobba Maria Francis, Marc Mezzarobba Bruno Grenet N/A 2bf9251 2bf9251552ea689272c058664f7c0b7f1d0e19a8 #25233

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.<z> = 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.

### comment:1 Changed 4 years ago by git

• Commit set to bde90c88d1e0ecd04c0633b54a479e23959a898c

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

 ​bde90c8 `Added gcd for univariate case over fraction field`

### comment:2 Changed 4 years ago by mfrancis

• Status changed from new to needs_review

### comment:3 Changed 4 years ago by msaaltink

• Status changed from needs_review to needs_work

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.

### comment:5 Changed 3 years ago by mfrancis

• Branch changed from u/mfrancis/fraction_field_univariate to u/mfrancis/fraction_field_univariatepoly
• Commit changed from bde90c88d1e0ecd04c0633b54a479e23959a898c to 1757afbf746eb60d097becc457577d5f733d6ab0

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.`

### comment:6 Changed 3 years ago by mfrancis

• Status changed from needs_work to needs_review

### comment:7 Changed 3 years ago by jdemeyer

• Status changed from needs_review to needs_work

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

```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)) ) :
```

### comment:8 Changed 3 years ago by mmezzarobba

• Authors changed from MARIA FRANCIS to Maria Francis, Marc Mezzarobba
• Branch changed from u/mfrancis/fraction_field_univariatepoly to u/mmezzarobba/23909-gcd_over_fraction_fields
• Commit changed from 1757afbf746eb60d097becc457577d5f733d6ab0 to 86d30f8a3c2d2aa0810101c11b25539f5f93c440
• Status changed from needs_work to needs_review

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`

### comment:9 Changed 3 years ago by mmezzarobba

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!

Last edited 3 years ago by mmezzarobba (previous) (diff)

### comment:10 Changed 3 years ago by mmezzarobba

• Status changed from needs_review to needs_work

### comment:11 Changed 3 years ago by git

• Commit changed from 86d30f8a3c2d2aa0810101c11b25539f5f93c440 to fdb3a93cdf52fc8e49af9bd7d99eb725c62d3184

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`

### comment:12 Changed 3 years ago by mmezzarobba

• Dependencies set to #25233

### comment:13 Changed 3 years ago by git

• Commit changed from fdb3a93cdf52fc8e49af9bd7d99eb725c62d3184 to e347c742d787c9feac33a11167050988ac94498e

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`

### comment:14 Changed 3 years ago by mmezzarobba

• Description modified (diff)
• Status changed from needs_work to needs_review

### comment:15 Changed 3 years ago by git

• Commit changed from e347c742d787c9feac33a11167050988ac94498e to ad86b39e17b2cf41738e55e33f37bfebb37f624d

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

 ​ad86b39 `fix gcd(0,0) for polynomials over fraction fields`

### comment:16 Changed 3 years ago by git

• Commit changed from ad86b39e17b2cf41738e55e33f37bfebb37f624d to 69ca4c1dc8222ea7d9b162142249984280f7df90

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`

### comment:18 Changed 3 years ago by mmezzarobba

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.

### comment:19 Changed 3 years ago by git

• Commit changed from 69ca4c1dc8222ea7d9b162142249984280f7df90 to b2599f40b78c3f147804c96a9517628483a0bc48

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`

### comment:20 follow-up: ↓ 22 Changed 3 years ago by bruno

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

### comment:21 Changed 3 years ago by git

• Commit changed from b2599f40b78c3f147804c96a9517628483a0bc48 to 2bf9251552ea689272c058664f7c0b7f1d0e19a8

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

 ​2bf9251 `#23909 improve docstring`

### comment:22 in reply to: ↑ 20 Changed 3 years ago by mmezzarobba

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

### comment:23 Changed 3 years ago by bruno

• Status changed from needs_review to positive_review

### comment:24 Changed 3 years ago by vbraun

• Status changed from positive_review to needs_work

Reviewer name is missing

### comment:25 Changed 3 years ago by mmezzarobba

• Reviewers set to Bruno Grenet
• Status changed from needs_work to positive_review

### comment:26 Changed 3 years ago by vbraun

• Branch changed from u/mmezzarobba/23909-gcd_over_fraction_fields to 2bf9251552ea689272c058664f7c0b7f1d0e19a8
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.