Opened 8 years ago
Closed 5 years ago
#13629 closed task (fixed)
provide xgcd for new polynomial rings through _xgcd_univariate_polynomial
Reported by:  saraedum  Owned by:  AlexGhitza 

Priority:  minor  Milestone:  sage6.4 
Component:  basic arithmetic  Keywords:  sd59 
Cc:  boerner  Merged in:  
Authors:  Julian Rueth  Reviewers:  Peter Bruin, Bruno Grenet 
Report Upstream:  N/A  Work issues:  
Branch:  828b5fc (Commits)  Commit:  828b5fc1a62567b98e35167cf686c59340b521f6 
Dependencies:  #13628, #18461, #18467  Stopgaps: 
Description
Currently, to add xgcd functionality for a new polynomial ring, one needs to add a specialized subclass of PolynomialElement.
The attached patch allows rings to provide a _xgcd_univariate_polynomial
method which will be called by PolynomialElement to compute xgcds.
Attachments (1)
Change History (39)
comment:1 Changed 8 years ago by
 Dependencies changed from #13628 to #13628, #13442
comment:2 Changed 8 years ago by
 Dependencies changed from #13628, #13442 to #13628
Changed 8 years ago by
comment:3 Changed 8 years ago by
 Status changed from new to needs_review
comment:4 Changed 8 years ago by
 Status changed from needs_review to needs_work
comment:5 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:6 Changed 6 years ago by
 Branch set to u/niles/ticket/13629
 Created changed from 10/19/12 20:27:51 to 10/19/12 20:27:51
 Modified changed from 08/13/13 15:35:53 to 08/13/13 15:35:53
comment:7 Changed 6 years ago by
 Commit set to 861d6989775ca4d9c9c81fd1cff998d8dd042751
rebased to sage 6.0 and converted to git branch; no other changes
merges cleanly in local repository in spite of what trac says
New commits:
c3df981  Trac #13441: refactored gcd to not use _gcd calls anymore

5b6e9c6  Trac #13628: refactored xgcd to not use _xgcd calls anymore.

861d698  Trac #13629: rings can provide _xgcd_univariate_polynomial for xgcd computations

comment:8 Changed 6 years ago by
 Commit changed from 861d6989775ca4d9c9c81fd1cff998d8dd042751 to 0570335d9d4a84c27c70d259da4a41b75493cd1b
Branch pushed to git repo; I updated commit sha1. New commits:
0570335  fix arguments for sage.categories.fields._xgcd_univariate_polynomial

comment:9 Changed 6 years ago by
the arguments for sage.categories.fields._xgcd_univariate_polynomial
were incompatible with the way it is used; I've changed them in a way that seems to be working
comment:10 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:11 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:12 Changed 6 years ago by
 Branch changed from u/niles/ticket/13629 to u/saraedum/ticket/13629
 Modified changed from 05/06/14 15:20:58 to 05/06/14 15:20:58
comment:13 Changed 6 years ago by
 Keywords sd59 added
 Status changed from needs_work to needs_review
comment:14 Changed 6 years ago by
 Commit changed from 0570335d9d4a84c27c70d259da4a41b75493cd1b to a5496dbd515728badf46890e8da171ef7eba61ef
Branch pushed to git repo; I updated commit sha1. New commits:
a5496db  fixed incorrect doctest format

comment:15 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:16 Changed 5 years ago by
There's a typo in the documentation of src/sage/rings/polynomial/polynomial_element.pyx
:
+ Compute an extended gcd of this polynomialn and ``other``.
Otherwise, I've the same comment as for #13442 on self
versus this polynomial
.
comment:17 Changed 5 years ago by
Also, the INPUT
and OUTPUT
blocks should not be indented (cf. comment:12:ticket:13442).
comment:18 Changed 5 years ago by
 Commit changed from a5496dbd515728badf46890e8da171ef7eba61ef to c6e9746a135a3169b0d58ccb34bd76a9d22f3a80
Branch pushed to git repo; I updated commit sha1. New commits:
c6e9746  Merge branch 'develop' into t/13629/ticket/13629

comment:19 Changed 5 years ago by
 Commit changed from c6e9746a135a3169b0d58ccb34bd76a9d22f3a80 to a3d778fd433b34edd55e4ccd87400969652830b2
Branch pushed to git repo; I updated commit sha1. New commits:
a3d778f  Merge branch 'develop' into t/13629/ticket/13629

comment:20 Changed 5 years ago by
 Cc boerner added
comment:21 Changed 5 years ago by
 Dependencies changed from #13628 to #13628, #18461
 Status changed from needs_review to needs_work
After resolving merge conflicts, one doctest fails due to the bug mentioned in #18461.
comment:22 Changed 5 years ago by
 Branch changed from u/saraedum/ticket/13629 to u/pbruin/13629xgcd_univariate_polynomial
 Commit changed from a3d778fd433b34edd55e4ccd87400969652830b2 to 011592eac5427af20416fc5eb8c424d9723f5876
The current branch passes all tests. However, I'm wondering whether Field._xgcd_univariate_polynomial
shouldn't be implemented as well (cf. #18461) for performance reasons.
comment:23 Changed 5 years ago by
 Reviewers set to Peter Bruin
comment:24 Changed 5 years ago by
I implemented Field._xgcd_univariate_polynomial
and got a noticeable speed increase. However, while writing doctests I ran into #18467.
comment:25 Changed 5 years ago by
 Commit changed from 011592eac5427af20416fc5eb8c424d9723f5876 to 828b5fc1a62567b98e35167cf686c59340b521f6
Branch pushed to git repo; I updated commit sha1. New commits:
828b5fc  Trac 13629: implement Field._xgcd_univariate_polynomial

comment:26 Changed 5 years ago by
 Dependencies changed from #13628, #18461 to #13628, #18461, #18467
 Status changed from needs_work to needs_review
I'm happy with the current state of the ticket, but it is probably good if someone checks my last two commits before this can get a positive review.
comment:27 followup: ↓ 28 Changed 5 years ago by
With the current state of this ticket, there are two implementations of _xgcd_univariate_polynomial
, one in the class Field
(in src/sage/rings/rings.pyx
) and one in the class ParentMethods
of the class Fields
(in src/sage/categories/fields.py
).
 In which case(s) will each of these implementations be used?
 Is the implementation in
Fields
really needed?
I note that the exact same questions are equally relevant for the positivereviewed (by myself!) ticket #18461. I simply did not think of that issue before.
comment:28 in reply to: ↑ 27 ; followup: ↓ 29 Changed 5 years ago by
Replying to bruno:
With the current state of this ticket, there are two implementations of
_xgcd_univariate_polynomial
, one in the classField
(insrc/sage/rings/rings.pyx
) and one in the classParentMethods
of the classFields
(insrc/sage/categories/fields.py
).
 In which case(s) will each of these implementations be used?
The implementation in sage.rings.ring.Field
is used if the base ring inherits from Field
.
The implementation in sage.categories.fields.Fields.ParentMethods
is used if the base ring is a field but does not inherit from Field
; the method is then looked up by the category framework.
The latter situation is sometimes detected only at runtime:
sage: R = Zmod(7) sage: R._xgcd_univariate_polynomial Traceback (most recent call last): ... AttributeError: 'IntegerModRing_generic_with_category' object has no attribute '_xgcd_univariate_polynomial' sage: R in Fields() True sage: R._xgcd_univariate_polynomial <bound method IntegerModRing_generic_with_category._xgcd_univariate_polynomial of Ring of integers modulo 7>
I suspect it is a feature (to avoid a potentially costly primality test) and not a bug that the method only appears after we have forced R
to refine its category...
 Is the implementation in
Fields
really needed?
I think it is, as the above example shows.
I note that the exact same questions are equally relevant for the positivereviewed (by myself!) ticket #18461. I simply did not think of that issue before.
I did have the above picture in mind when working on both tickets, and I am afraid the situation is unavoidable without lots of refactoring.
One thing that could be done to reduce duplication is making quo_rem
the primitive operation that base rings of polynomial rings should implement, instead of the two operations _[x]gcd_univariate_polynomial
. That would be something for a followup ticket, though.
comment:29 in reply to: ↑ 28 Changed 5 years ago by
Replying to pbruin:
I suspect it is a feature (to avoid a potentially costly primality test) and not a bug that the method only appears after we have forced
R
to refine its category...
OK, thank you for the explanation.
I note that the exact same questions are equally relevant for the positivereviewed (by myself!) ticket #18461. I simply did not think of that issue before.
I did have the above picture in mind when working on both tickets, and I am afraid the situation is unavoidable without lots of refactoring.
One thing that could be done to reduce duplication is making
quo_rem
the primitive operation that base rings of polynomial rings should implement, instead of the two operations_[x]gcd_univariate_polynomial
. That would be something for a followup ticket, though.
I am not sure what would be the best solution to avoid code duplication in such cases, though I totally agree that it does not belong to this ticket!
I'm running tests to check everything is OK.
comment:30 followup: ↓ 31 Changed 5 years ago by
 Status changed from needs_review to needs_work
The current branch does not pass the tests. The failed test is in src/sage/rings/ring.pyx
, lines 21962203:
sage: for A in (RR, CC, QQbar): ....: g = A._gcd_univariate_polynomial ....: R.<x> = A[] ....: z = R.zero() ....: assert(g(2*x, 2*x^2) == x and ....: g(z, 2*x) == x and ....: g(2*x, z) == x and ....: g(z, z) == z)
More precisely, I've got the following severe bug:
sage: R.<x> = RR[] sage: z, h = R(0), R(1/2) sage: (xx, hh, zz) = RR._xgcd_univariate_polynomial(2*x, 2*x^2) sage: zz == z False sage: zzz BOOOM! (SegFault)
The crash log is empty.
comment:31 in reply to: ↑ 30 ; followup: ↓ 32 Changed 5 years ago by
comment:32 in reply to: ↑ 31 ; followup: ↓ 34 Changed 5 years ago by
Replying to pbruin:
Replying to bruno:
The current branch does not pass the tests.
You have to merge #18467 (which is also in 6.8.beta1)...
Hmmm, there my git knowledge is not sufficient I guess. So let me take the opportunity to ask a few questions:
 My
develop
branch is uptodate (6.8.beta1). When I switch to this branch (git checkout t/13629/...
) I need to recompile a lot. I there a way to decrease the compilation needed to work on such tickets?  Since the ticket depends on #18467, shouldn't you add a commit to merge #18467?
 What is the correct (or the best one if there are several) way to merge #18467, so that I can correctly test this branch?
Thanks in advance!
comment:33 Changed 5 years ago by
 Reviewers changed from Peter Bruin to Peter Bruin, Bruno Grenet
 Status changed from needs_work to positive_review
OK, I've been able to test the ticket with #18467 merged and all tests pass. This is fine to me!
comment:34 in reply to: ↑ 32 ; followup: ↓ 35 Changed 5 years ago by
Replying to bruno:
 My
develop
branch is uptodate (6.8.beta1). When I switch to this branch (git checkout t/13629/...
) I need to recompile a lot. I there a way to decrease the compilation needed to work on such tickets?
git pull trac u/pbruin/13629xgcd_univariate_polynomial
; this merges with the branch that you have currently checked out (develop
in this case)
People have differing opinions about this; I prefer to avoid unnecessary merge commits.
 What is the correct (or the best one if there are several) way to merge #18467, so that I can correctly test this branch?
If you used the command as in (1) this should not be necessary, but in general you can do git pull trac BRANCH
where BRANCH
is the name of the branch on Trac that you want to merge. (If you want to merge a local branch, the analogous command is git merge BRANCH
.)
comment:35 in reply to: ↑ 34 ; followup: ↓ 36 Changed 5 years ago by
Thank you for the clarifications. One point still:
Replying to pbruin:
Replying to bruno:
 My
develop
branch is uptodate (6.8.beta1). When I switch to this branch (git checkout t/13629/...
) I need to recompile a lot. I there a way to decrease the compilation needed to work on such tickets?
git pull trac u/pbruin/13629xgcd_univariate_polynomial
; this merges with the branch that you have currently checked out (develop
in this case)
Doesn't this modify my local develop
branch? What I did finally to review the ticket is to create a new branch (git branch ticket/13629
), then pull your branch (git trac pull 13629
, which I guess does the same as what you propose). So finally this is close to what you mention.
My question though: Isn't it dangerous to modify the local develop
branch? (I wouldn't like to take the risk to mess up some things I do not understand ;).)
Thanks again!
comment:36 in reply to: ↑ 35 ; followup: ↓ 37 Changed 5 years ago by
Replying to bruno:
Doesn't this modify my local
develop
branch? What I did finally to review the ticket is to create a new branch (git branch ticket/13629
), then pull your branch (git trac pull 13629
, which I guess does the same as what you propose). So finally this is close to what you mention.My question though: Isn't it dangerous to modify the local
develop
branch? (I wouldn't like to take the risk to mess up some things I do not understand ;).)
Yes, I should have said that you should create a new branch first, which seems to be what you did (but be careful to check out the branch first with git checkout ticket/13629
; you can actually create the new branch at the same time with git checkout b 13629
).
comment:37 in reply to: ↑ 36 Changed 5 years ago by
Replying to pbruin:
Replying to bruno:
Doesn't this modify my local
develop
branch? What I did finally to review the ticket is to create a new branch (git branch ticket/13629
), then pull your branch (git trac pull 13629
, which I guess does the same as what you propose). So finally this is close to what you mention.My question though: Isn't it dangerous to modify the local
develop
branch? (I wouldn't like to take the risk to mess up some things I do not understand ;).)Yes, I should have said that you should create a new branch first, which seems to be what you did (but be careful to check out the branch first with
git checkout ticket/13629
; you can actually create the new branch at the same time withgit checkout b 13629
).
Right, I did not mention the git checkout ticket/13629
that I indeed did. Thanks again, and thank you for the shortcut! The way it works is now clearer.
comment:38 Changed 5 years ago by
 Branch changed from u/pbruin/13629xgcd_univariate_polynomial to 828b5fc1a62567b98e35167cf686c59340b521f6
 Resolution set to fixed
 Status changed from positive_review to closed
I want to remove {{self}} from the docstrings.