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:  sage8.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: 
Description (last modified by )
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
 Commit set to bde90c88d1e0ecd04c0633b54a479e23959a898c
comment:2 Changed 4 years ago by
 Status changed from new to needs_review
comment:3 Changed 4 years ago by
 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
 Cc mmezzarobba added
comment:5 Changed 3 years ago by
 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
 Status changed from needs_work to needs_review
comment:7 Changed 3 years ago by
 Status changed from needs_review to needs_work
The documentation is badly misformatted. See http://doc.sagemath.org/html/en/developer/coding_basics.html#documentationstrings
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
 Branch changed from u/mfrancis/fraction_field_univariatepoly to u/mmezzarobba/23909gcd_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
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!
comment:10 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:11 Changed 3 years ago by
 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
 Dependencies set to #25233
comment:13 Changed 3 years ago by
 Commit changed from fdb3a93cdf52fc8e49af9bd7d99eb725c62d3184 to e347c742d787c9feac33a11167050988ac94498e
comment:14 Changed 3 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
comment:15 Changed 3 years ago by
 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
 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:17 Changed 3 years ago by
See also #25318 for an additional improvement.
comment:18 Changed 3 years ago by
As far as I can tell, the last two patchbot failures are not related to this ticket—i.e. the tests still pass with sage8.3.beta3.
comment:19 Changed 3 years ago by
 Commit changed from 69ca4c1dc8222ea7d9b162142249984280f7df90 to b2599f40b78c3f147804c96a9517628483a0bc48
comment:20 followup: ↓ 22 Changed 3 years ago by
Looks good to me, except the docstring. Could you add a short description?
comment:21 Changed 3 years ago by
 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
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
 Status changed from needs_review to positive_review
comment:24 Changed 3 years ago by
 Status changed from positive_review to needs_work
Reviewer name is missing
comment:25 Changed 3 years ago by
 Reviewers set to Bruno Grenet
 Status changed from needs_work to positive_review
comment:26 Changed 3 years ago by
 Branch changed from u/mmezzarobba/23909gcd_over_fraction_fields to 2bf9251552ea689272c058664f7c0b7f1d0e19a8
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Added gcd for univariate case over fraction field