provide xgcd for new polynomial rings through _xgcd_univariate_polynomial

[saraedum]

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.

Depends on #13628
Depends on #18461
Depends on #18467

CC: @sagetrac-boerner

Component: basic arithmetic

Keywords: sd59

Author: Julian Rueth

Branch/Commit: 828b5fc

Reviewer: Peter Bruin, Bruno Grenet

Issue created by migration from https://trac.sagemath.org/ticket/13629

[saraedum]

Changed dependencies from #13628 to #13628, #13442

[saraedum]

Changed dependencies from #13628, #13442 to #13628

[saraedum]

Attachment: trac_13629.patch.gz

[saraedum]

comment:4

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

[nilesjohnson]

Branch: u/niles/ticket/13629

[nilesjohnson]

comment:7

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

[nilesjohnson]

Commit: 861d698

[sagetrac-git]

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

0570335

fix arguments for sage.categories.fields._xgcd_univariate_polynomial

[sagetrac-git]

Changed commit from 861d698 to 0570335

[nilesjohnson]

comment:9

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

[saraedum]

Changed branch from u/niles/ticket/13629 to u/saraedum/ticket/13629

[saraedum]

Changed keywords from none to sd59

[sagetrac-git]

Changed commit from 0570335 to a5496db

[sagetrac-git]

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

a5496db

fixed incorrect doctest format

[pjbruin]

Changed commit from a3d778f to 011592e

[pjbruin]

Changed branch from u/saraedum/ticket/13629 to u/pbruin/13629-xgcd_univariate_polynomial

[pjbruin]

Reviewer: Peter Bruin

[pjbruin]

comment:24

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

[sagetrac-git]

Changed commit from 011592e to 828b5fc

[sagetrac-git]

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

828b5fc

Trac 13629: implement Field._xgcd_univariate_polynomial

[pjbruin]

comment:26

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.

[pjbruin]

Changed dependencies from #13628, #18461 to #13628, #18461, #18467

[bgrenet]

comment:27

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.

[pjbruin]

comment:28

Replying to @bgrenet:

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

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

[bgrenet]

comment:29

Replying to @pjbruin:

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.

[bgrenet]

comment:30

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.

[pjbruin]

comment:31

Replying to @bgrenet:

The current branch does not pass the tests.

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

[bgrenet]

comment:32

Replying to @pjbruin:

Replying to @bgrenet:

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 PolynomialRealDense.quo_rem() returns zero polynomials with wrong degree #18467, shouldn't you add a commit to merge PolynomialRealDense.quo_rem() returns zero polynomials with wrong degree #18467?
3. What is the correct (or the best one if there are several) way to merge PolynomialRealDense.quo_rem() returns zero polynomials with wrong degree #18467, so that I can correctly test this branch?

Thanks in advance!

[bgrenet]

Changed reviewer from Peter Bruin to Peter Bruin, Bruno Grenet

[bgrenet]

comment:33

OK, I've been able to test the ticket with #18467 merged and all tests pass. This is fine to me!

[pjbruin]

comment:34

Replying to @bgrenet:

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)

2. Since the ticket depends on PolynomialRealDense.quo_rem() returns zero polynomials with wrong degree #18467, shouldn't you add a commit to merge PolynomialRealDense.quo_rem() returns zero polynomials with wrong degree #18467?

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

3. What is the correct (or the best one if there are several) way to merge PolynomialRealDense.quo_rem() returns zero polynomials with wrong degree #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.)

[bgrenet]

comment:35

Thank you for the clarifications. One point still:

Replying to @pjbruin:

Replying to @bgrenet:

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!

[pjbruin]

comment:36

Replying to @bgrenet:

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

[bgrenet]

comment:37

Replying to @pjbruin:

Replying to @bgrenet:

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.

[vbraun]

Changed branch from u/pbruin/13629-xgcd_univariate_polynomial to 828b5fc