Opened 4 years ago

Closed 3 years ago

#23909 closed enhancement (fixed)

GCD for univariate polynomials over fraction fields

Reported by: mfrancis Owned by:
Priority: minor Milestone: sage-8.1
Component: algebra Keywords: gcd, univariate polynomials, fraction fields as coefficients
Cc: mmezzarobba Merged in:
Authors: Maria Francis, Marc Mezzarobba Reviewers: Bruno Grenet
Report Upstream: N/A Work issues:
Branch: 2bf9251 (Commits, GitHub, GitLab) Commit: 2bf9251552ea689272c058664f7c0b7f1d0e19a8
Dependencies: #25233 Stopgaps:

Status badges

Description (last modified by mmezzarobba)

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.

Change History (26)

comment:1 Changed 4 years ago by git

  • Commit set to bde90c88d1e0ecd04c0633b54a479e23959a898c

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

bde90c8Added 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:4 Changed 3 years ago by mmezzarobba

  • Cc mmezzarobba added

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:

1757afbMade 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

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

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:

86d30f8speed 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:

4ac14ccSupport repeated variable names in FlatteningMorphism
e26d75acached flattening_morphism() method for univariate polynomial rings
54a8262use FlatteningMorphism in gcd over stacked polynomial rings
fdb3a93speed 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:

26a3ed1use FlatteningMorphism in gcd over stacked polynomial rings
e347c74speed 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:

ad86b39fix 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:

0d56c5fSupport repeated variable names in FlatteningMorphism
751fe89cached flattening_morphism() method for univariate polynomial rings
8de9bbfuse FlatteningMorphism in gcd over stacked polynomial rings
1379f64speed up gcd() of polynomials over fraction fields
69ca4c1fix gcd(0,0) for polynomials over fraction fields

comment:17 Changed 3 years ago by mmezzarobba

See also #25318 for an additional improvement.

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:

68fc7a1speed up gcd() of polynomials over fraction fields
b2599f4fix gcd(0,0) for polynomials over fraction fields

comment:20 follow-up: 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

Replying to bruno:

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

Done, thanks for your commment!

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.