Opened 7 years ago

Closed 4 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: sage-6.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.

This is similar to #10635, #13442.

Attachments (1)

trac_13629.patch (7.1 KB) - added by saraedum 7 years ago.

Download all attachments as: .zip

Change History (39)

comment:1 Changed 7 years ago by saraedum

  • Dependencies changed from #13628 to #13628, #13442

comment:2 Changed 7 years ago by saraedum

  • Dependencies changed from #13628, #13442 to #13628

Changed 7 years ago by saraedum

comment:3 Changed 7 years ago by saraedum

  • Status changed from new to needs_review

comment:4 Changed 7 years ago by saraedum

  • Status changed from needs_review to needs_work

I want to remove {{self}} from the docstrings.

comment:5 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 6 years ago by niles

  • 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 niles

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

c3df981Trac #13441: refactored gcd to not use _gcd calls anymore
5b6e9c6Trac #13628: refactored xgcd to not use _xgcd calls anymore.
861d698Trac #13629: rings can provide _xgcd_univariate_polynomial for xgcd computations

comment:8 Changed 6 years ago by git

  • Commit changed from 861d6989775ca4d9c9c81fd1cff998d8dd042751 to 0570335d9d4a84c27c70d259da4a41b75493cd1b

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

0570335fix arguments for sage.categories.fields._xgcd_univariate_polynomial

comment:9 Changed 6 years ago by niles

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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:12 Changed 5 years ago by saraedum

  • 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 5 years ago by saraedum

  • Keywords sd59 added
  • Status changed from needs_work to needs_review

comment:14 Changed 5 years ago by git

  • Commit changed from 0570335d9d4a84c27c70d259da4a41b75493cd1b to a5496dbd515728badf46890e8da171ef7eba61ef

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

a5496dbfixed incorrect doctest format

comment:15 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:16 Changed 5 years ago by bruno

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.

Last edited 5 years ago by bruno (previous) (diff)

comment:17 Changed 5 years ago by pbruin

Also, the INPUT and OUTPUT blocks should not be indented (cf. comment:12:ticket:13442).

comment:18 Changed 5 years ago by git

  • Commit changed from a5496dbd515728badf46890e8da171ef7eba61ef to c6e9746a135a3169b0d58ccb34bd76a9d22f3a80

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

c6e9746Merge branch 'develop' into t/13629/ticket/13629

comment:19 Changed 5 years ago by git

  • Commit changed from c6e9746a135a3169b0d58ccb34bd76a9d22f3a80 to a3d778fd433b34edd55e4ccd87400969652830b2

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

a3d778fMerge branch 'develop' into t/13629/ticket/13629

comment:20 Changed 5 years ago by saraedum

  • Cc boerner added

comment:21 Changed 4 years ago by pbruin

  • 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 4 years ago by pbruin

  • Branch changed from u/saraedum/ticket/13629 to u/pbruin/13629-xgcd_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 4 years ago by pbruin

  • Reviewers set to Peter Bruin

comment:24 Changed 4 years ago by pbruin

I implemented Field._xgcd_univariate_polynomial and got a noticeable speed increase. However, while writing doctests I ran into #18467.

comment:25 Changed 4 years ago by git

  • Commit changed from 011592eac5427af20416fc5eb8c424d9723f5876 to 828b5fc1a62567b98e35167cf686c59340b521f6

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

828b5fcTrac 13629: implement Field._xgcd_univariate_polynomial

comment:26 Changed 4 years ago by pbruin

  • 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 follow-up: Changed 4 years ago by bruno

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

  1. In which case(s) will each of these implementations be used?
  2. Is the implementation in Fields really needed?

I note that the exact same questions are equally relevant for the positive-reviewed (by myself!) ticket #18461. I simply did not think of that issue before.

Last edited 4 years ago by bruno (previous) (diff)

comment:28 in reply to: ↑ 27 ; follow-up: Changed 4 years ago by pbruin

Replying to bruno:

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

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

  1. 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 positive-reviewed (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 follow-up ticket, though.

comment:29 in reply to: ↑ 28 Changed 4 years ago by bruno

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 positive-reviewed (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 follow-up 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 follow-up: Changed 4 years ago by bruno

  • 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 2196-2203:

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: zz-z
BOOOM! (SegFault)

The crash log is empty.

comment:31 in reply to: ↑ 30 ; follow-up: Changed 4 years ago by pbruin

Replying to bruno:

The current branch does not pass the tests.

You have to merge #18467 (which is also in 6.8.beta1)...

comment:32 in reply to: ↑ 31 ; follow-up: Changed 4 years ago by bruno

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:

  1. My develop branch is up-to-date (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?
  2. Since the ticket depends on #18467, shouldn't you add a commit to merge #18467?
  3. 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 4 years ago by bruno

  • 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 ; follow-up: Changed 4 years ago by pbruin

Replying to bruno:

  1. My develop branch is up-to-date (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/13629-xgcd_univariate_polynomial; this merges with the branch that you have currently checked out (develop in this case)

  1. Since the ticket depends on #18467, shouldn't you add a commit to merge #18467?

People have differing opinions about this; I prefer to avoid unnecessary merge commits.

  1. 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 ; follow-up: Changed 4 years ago by bruno

Thank you for the clarifications. One point still:

Replying to pbruin:

Replying to bruno:

  1. My develop branch is up-to-date (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/13629-xgcd_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 ; follow-up: Changed 4 years ago by 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 with git checkout -b 13629).

comment:37 in reply to: ↑ 36 Changed 4 years ago by bruno

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 with git 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 4 years ago by vbraun

  • Branch changed from u/pbruin/13629-xgcd_univariate_polynomial to 828b5fc1a62567b98e35167cf686c59340b521f6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.