Opened 4 years ago
Closed 4 years ago
#24264 closed enhancement (fixed)
Allow "generic" PolynomialRing implementation
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  basic arithmetic  Keywords:  
Cc:  embray, tscrim  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  0efda1b (Commits, GitHub, GitLab)  Commit:  0efda1be627e00c9ee03bb70900d37663f638470 
Dependencies:  Stopgaps: 
Description (last modified by )
It is possible to specify a specific backend like PolynomialRing(QQ, 'x', implementation="singular")
but the opposite (asking for a generic Sage implementation) is not. Fix this by allowing implementation="generic"
.
This requires various fixes involving the implementation
keyword being ignored or breaking caching. In particular, we fix this caching bug:
sage: p = 2^64 + 13 sage: A = GF(p^2) sage: B = GF(p^3) sage: R = A.modulus().parent() sage: S = B.modulus().parent() sage: R is S False
We also introduce a new implementation "GF2X" for the GF2X package. This used be called "NTL" which we still allow as alias.
Change History (59)
comment:1 Changed 4 years ago by
comment:2 Changed 4 years ago by
 Description modified (diff)
comment:3 Changed 4 years ago by
 Cc tscrim added
comment:4 Changed 4 years ago by
comment:5 Changed 4 years ago by
This is harder than expected due to caching. Currently, the caching does not take into account the implementation
keyword. That is an existing bug, but it makes it pointless to add more support for the implementation
keyword.
comment:6 followup: ↓ 8 Changed 4 years ago by
Wouldn't it make sense to fix that? It doesn't need to use the "implementation" keyword per se, but it would make sense if the type a method was called on was also cached?
I'm likely missing something though since I don't know exactly what you mean in this case by "caching".
comment:7 Changed 4 years ago by
 Description modified (diff)
comment:8 in reply to: ↑ 6 Changed 4 years ago by
Replying to embray:
Wouldn't it make sense to fix that?
Of course. I'm just saying that this makes it harder than I initially expected.
comment:9 Changed 4 years ago by
 Branch set to u/jdemeyer/allow__generic__polynomialring_implementation
comment:10 Changed 4 years ago by
 Commit set to f8449e9821e3298266552c326078aea6360645e0
 Status changed from new to needs_review
New commits:
f8449e9  Allow "generic" PolynomialRing implementation

comment:11 Changed 4 years ago by
 Description modified (diff)
comment:12 Changed 4 years ago by
 Status changed from needs_review to needs_work
comment:13 Changed 4 years ago by
 Commit changed from f8449e9821e3298266552c326078aea6360645e0 to b8990cb104c69cea819be6d7320188f13209e2b6
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b8990cb  Allow "generic" PolynomialRing implementation

comment:14 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:15 followup: ↓ 20 Changed 4 years ago by
This change:

src/sage/algebras/free_algebra.py
diff git a/src/sage/algebras/free_algebra.py b/src/sage/algebras/free_algebra.py index e6c66e9..09db35d 100644
a b class FreeAlgebraFactory(UniqueFactory): 269 269 # test if we can use libSingular/letterplace 270 270 if implementation == "letterplace": 271 271 args = [arg for arg in (arg1, arg2) if arg is not None] 272 kwds = dict( sparse=sparse,order=order, implementation="singular")272 kwds = dict(order=order, implementation="singular") 273 273 if name is not None: 274 274 kwds["name"] = name 275 275 if names is not None:
seems to cause multiple failures with the free algebra:
sage t long src/sage/algebras/free_algebra.py # 12 doctests failed sage t long src/sage/algebras/letterplace/letterplace_ideal.pyx # Bad exit: 14 sage t long src/sage/algebras/letterplace/free_algebra_letterplace.pyx # 19 doctests failed sage t long src/sage/algebras/letterplace/free_algebra_element_letterplace.pyx # 31 doctests failed
See patchbots.
Also, we (and singular?) only have sparse implementations for multivariate polynomials, right?
comment:16 Changed 4 years ago by
 Status changed from needs_review to needs_work
comment:17 Changed 4 years ago by
 Commit changed from b8990cb104c69cea819be6d7320188f13209e2b6 to a299cb4c0c04de8331933d2ba70e2d99b57e2acf
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a299cb4  Allow "generic" PolynomialRing implementation

comment:18 Changed 4 years ago by
 Commit changed from a299cb4c0c04de8331933d2ba70e2d99b57e2acf to 21b4952d4fab7a14bdfd0611d2e2f1e01f74dee5
Branch pushed to git repo; I updated commit sha1. New commits:
21b4952  Fix Wsigncompare compiler warning

comment:19 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:20 in reply to: ↑ 15 Changed 4 years ago by
Replying to tscrim:
seems to cause multiple failures with the free algebra:
Fixed by allowing sparse=None
to mean sparse=True
in the multivariate case.
comment:21 Changed 4 years ago by
Patchbot is green now.
comment:22 followups: ↓ 23 ↓ 32 Changed 4 years ago by
What are your thoughts about changing _implementation_names
to _implementation
, which only takes a string? It is only used to differentiate between FLINT and NTL implementations in coercion. I think it could simplify the code overall.
Furthermore, how do you feel about instead of storing a key for all implementation keywords possible, we instead standardize the implementation keyword to always give the actual implementation. I know it is a little more brittle, but I think it will make the code more clean and would work well with the above suggestion. I haven't yet fully attempted this, but I will be happy to do this if you do not object.
One thing that definitely needs fixing: By allowing generic coercions, we are introducing a memory leak via cyclic coercion between the generic and FLINT implementations:
sage: RF.<x> = PolynomialRing(ZZ, implementation='FLINT') sage: RG.<x> = PolynomialRing(ZZ, implementation='generic') sage: RF.coerce_map_from(RG) sage: RF.has_coerce_map_from(RG) True sage: RG.has_coerce_map_from(RF) True
I've been told that this circular coercion gives a memory leak because the co(?)domain is cached by the coercion model. Although I cannot reproduce it:
sage: import gc sage: for i in range(10000): ....: if i % 100 == 0: ....: get_memory_usage() ....: R = PolynomialRing(ZZ, 'x%s'%i, implementation='FLINT') ....: S = PolynomialRing(ZZ, 'x%s'%i, implementation='generic') ....: assert R is not S ....: assert R.coerce_map_from(S) is not None ....: assert S.coerce_map_from(R) is not None ....: del R ....: del S ....: _ = gc.collect() 5872.29296875 5872.29296875 5872.29296875 5872.29296875 ...
However, it does introduce a *very* subtle reason why code could suddenly become slow by multiplying things in the opposite order. We will have to update things accordingly in that spot in PolynomialRing._coerce_map_from_
.
comment:23 in reply to: ↑ 22 ; followup: ↓ 24 Changed 4 years ago by
Replying to tscrim:
Furthermore, how do you feel about instead of storing a key for all implementation keywords possible, we instead standardize the implementation keyword to always give the actual implementation.
Well, this will slow down creating polynomial rings. Every time that you create a polynomial ring with implementation=None
(which is the default, so the most common case), you will need to run some code to figure out the implementation.
Let me give a counterproposal: instead of making _implementation_names
an attribute, we create a static method on the polynomial ring class:
# Assuming that the implementation for a given polynomial ring class # depends only on the base_ring, which is currently the case. @staticmethod def _implementation_names(base_ring, implementation): # Default implementation for generic polynomial rings if implementation is None or implementation == "generic": return ["generic", None] raise ValueError("unknown implementation {!r}".format(implementation))
I think that this will lead to cleaner code without the performance loss of normalizing the implementation
every time.
comment:24 in reply to: ↑ 23 Changed 4 years ago by
Replying to jdemeyer:
Replying to tscrim:
Furthermore, how do you feel about instead of storing a key for all implementation keywords possible, we instead standardize the implementation keyword to always give the actual implementation.
Well, this will slow down creating polynomial rings. Every time that you create a polynomial ring with
implementation=None
(which is the default, so the most common case), you will need to run some code to figure out the implementation.
Ah, that is a good point about having to process the input.
Let me give a counterproposal: instead of making
_implementation_names
an attribute, we create a static method on the polynomial ring class:# Assuming that the implementation for a given polynomial ring class # depends only on the base_ring, which is currently the case. @staticmethod def _implementation_names(base_ring, implementation): # Default implementation for generic polynomial rings if implementation is None or implementation == "generic": return ["generic", None] raise ValueError("unknown implementation {!r}".format(implementation))I think that this will lead to cleaner code without the performance loss of normalizing the
implementation
every time.
+1 Do you want me to do this or will you?
comment:25 followup: ↓ 28 Changed 4 years ago by
Let me give this a try.
comment:26 Changed 4 years ago by
 Description modified (diff)
 Status changed from needs_review to needs_work
comment:27 Changed 4 years ago by
 Commit changed from 21b4952d4fab7a14bdfd0611d2e2f1e01f74dee5 to bfd388f57c354d96eaf85442b17d7ca6dd2fdc1e
comment:28 in reply to: ↑ 25 Changed 4 years ago by
 Status changed from needs_work to needs_review
Replying to jdemeyer:
Let me give this a try.
Done. This was more work than I initially thought, but I am happy with the result. The code looks cleaner than before.
comment:29 Changed 4 years ago by
 Commit changed from bfd388f57c354d96eaf85442b17d7ca6dd2fdc1e to a0aefd8670fda042b00e1730b682eb5d47824627
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a0aefd8  Allow "generic" PolynomialRing implementation

comment:30 followup: ↓ 31 Changed 4 years ago by
It definitely is cleaner to me as well. Some comments:
 This seems fragile:
I would instead do
implementation = self._implementation_names(implementation, base_ring)[0] if implementation == "NTL":
implementation = self._implementation_names(implementation, base_ring)[0] if "NTL" in implementation:
 The cyclic coercion (comment:22) should get a doctest for only the generic to FLINT (if I am reading the code correctly).
 This feels a bit fragile to me
I'm guessing you are doing this to avoid a circular import? What about doing something similar to what is currently there and checking the implementation name?
if self.element_class.__name__ != 'Polynomial_integer_dense_flint':
 Some
_implementation_names_impl
have doctests and others do not (including some with mildly nontrivial behavior).
Can you also explain why you have the @classmethod
and the @staticmethod
? I'm not quite sure I understand why we need the redirection.
comment:31 in reply to: ↑ 30 ; followup: ↓ 33 Changed 4 years ago by
Replying to tscrim:
 This seems fragile:
I would instead doimplementation = self._implementation_names(implementation, base_ring)[0] if implementation == "NTL":implementation = self._implementation_names(implementation, base_ring)[0] if "NTL" in implementation:
Why? I don't understand your objection.
 Some
_implementation_names_impl
have doctests and others do not (including some with mildly nontrivial behavior).
Well, all of them are tested somewhere. Some are tested explicitly by calling _implementation_names_impl
; some are tested indirectly by constructing an instance of a polynomial ring class; still others are testing using the polynomial ring constructor.
Can you also explain why you have the
@classmethod
and the@staticmethod
? I'm not quite sure I understand why we need the redirection.
It was just simpler that way. First of all, the actual implementations can just return NotImplemented
instead of raising an exception. This also simplifies one check in the polynomial constructor where I'm using list comprehension to check for NotImplemented
. You cannot use list comprehension with a condition "raises ValueError
".
Second, the wrapper method _implementation_names()
does a sanity check of the output of _implementation_names_impl()
: it checks that the given implementation
is in the output list.
comment:32 in reply to: ↑ 22 ; followup: ↓ 34 Changed 4 years ago by
Replying to tscrim:
One thing that definitely needs fixing: By allowing generic coercions, we are introducing a memory leak via cyclic coercion between the generic and FLINT implementations:
That is a very deep rabbit hole.
First of all, note that cyclic coercion is already possible in other cases:
sage: R = PolynomialRing(GF(3), 't', implementation='FLINT') sage: S = PolynomialRing(GF(3), 't', implementation='NTL') sage: R Univariate Polynomial Ring in t over Finite Field of size 3 sage: S Univariate Polynomial Ring in t over Finite Field of size 3 (using NTL) sage: R.has_coerce_map_from(S) True sage: S.has_coerce_map_from(R) True
There are two related issues when trying to fix this:
(A) The polynomial ring itself does not store its implementation or any other information which could help to determine in which way a coercion should go.
(B) Pickling doesn't work correctly for nondefault implementations:
# Continuing the example above sage: loads(dumps(S)) is S False sage: loads(dumps(S)) is R True
Currently, one could fix (A) by not allowing coercions between different implementations. But then (B) gives trouble because then there isn't even a coercion between loads(dumps(S))
and S
.
Suggestions??
comment:33 in reply to: ↑ 31 Changed 4 years ago by
Replying to jdemeyer:
Replying to tscrim:
 This seems fragile:
I would instead doimplementation = self._implementation_names(implementation, base_ring)[0] if implementation == "NTL":implementation = self._implementation_names(implementation, base_ring)[0] if "NTL" in implementation:Why? I don't understand your objection.
I either missed, didn't remember, or didn't quite understand the implication of the "The first element in the list is the canonical name." part of the OUTPUT
. So I thought you were using an undocumented specification.
 Some
_implementation_names_impl
have doctests and others do not (including some with mildly nontrivial behavior).Well, all of them are tested somewhere. Some are tested explicitly by calling
_implementation_names_impl
; some are tested indirectly by constructing an instance of a polynomial ring class; still others are testing using the polynomial ring constructor.
Would it be possible to have at least one of those tests local to each of these functions? It would make it easier to debug if something broke later on.
Can you also explain why you have the
@classmethod
and the@staticmethod
? I'm not quite sure I understand why we need the redirection.It was just simpler that way. First of all, the actual implementations can just
return NotImplemented
instead of raising an exception. This also simplifies one check in the polynomial constructor where I'm using list comprehension to check forNotImplemented
. You cannot use list comprehension with a condition "raisesValueError
".Second, the wrapper method
_implementation_names()
does a sanity check of the output of_implementation_names_impl()
: it checks that the givenimplementation
is in the output list.
Thank you for the explanations. Makes sense to me, and it made it easy to see where these features are being used.
comment:34 in reply to: ↑ 32 ; followup: ↓ 35 Changed 4 years ago by
Replying to jdemeyer:
Replying to tscrim:
One thing that definitely needs fixing: By allowing generic coercions, we are introducing a memory leak via cyclic coercion between the generic and FLINT implementations:
That is a very deep rabbit hole.
First of all, note that cyclic coercion is already possible in other cases:
sage: R = PolynomialRing(GF(3), 't', implementation='FLINT') sage: S = PolynomialRing(GF(3), 't', implementation='NTL') sage: R Univariate Polynomial Ring in t over Finite Field of size 3 sage: S Univariate Polynomial Ring in t over Finite Field of size 3 (using NTL) sage: R.has_coerce_map_from(S) True sage: S.has_coerce_map_from(R) True
I know some people would consider that a bug, and even if is not, it could create strange behavior and slowdowns because of moving between implementations.
There are two related issues when trying to fix this:
(A) The polynomial ring itself does not store its implementation or any other information which could help to determine in which way a coercion should go.
It has to store something in order to get the different string representations. As for determining which way to make the coercion is a bit more arbitrary, but something we can do in the _coerce_map_from_
.
(B) Pickling doesn't work correctly for nondefault implementations:
# Continuing the example above sage: loads(dumps(S)) is S False sage: loads(dumps(S)) is R TrueCurrently, one could fix (A) by not allowing coercions between different implementations. But then (B) gives trouble because then there isn't even a coercion between
loads(dumps(S))
andS
.
That's a bug (and somewhat horrifying).
Suggestions??
(B) deserves a ticket all on its own. Although (A) is currently addressed for ZZ
rings:
sage: R = PolynomialRing(ZZ, 't', implementation="FLINT") sage: S = PolynomialRing(ZZ, 't', implementation="NTL") sage: R.has_coerce_map_from(S) True sage: S.has_coerce_map_from(R) False
I can't think of a simple way with the current framework that we can have an ordering on the implementations that would correspond to the coercion order. I feel like we would need to add another @staticmethod
specifying this (with a default of [None]
when there is only 1 implementation, the default).
I am also happy addressing (A) more thoroughly on a followup if we just add a test for
sage: T = PolynomialRing(ZZ, 't', implementation="generic")
and the noncyclic coercion with R and S above.
comment:35 in reply to: ↑ 34 Changed 4 years ago by
Replying to tscrim:
I am also happy addressing (A) more thoroughly on a followup if we just add a test for
sage: T = PolynomialRing(ZZ, 't', implementation="generic")and the noncyclic coercion with R and S above.
Yes, I would rather do that. This ticket is already getting quite big...
comment:36 Changed 4 years ago by
comment:37 Changed 4 years ago by
Part of the mess in polynomial rings is that the logic for constructing them is separated in different places:
 The constructor
PolynomialRing
 The
_implementation_names_impl()
method of the polynomial ring.
 The
__init__
method of the polynomial ring.
There are also two nonequivalent ways to pass an implementation: using the implementation
keyword or using the element_class
keyword.
comment:38 Changed 4 years ago by
I feel like only PolynomialRing
should take an implementation
and not __init__
. Instead, the implementation
should be translated somewhere to an element_class
which is passed to __init__
.
But that will be for a followup.
comment:39 Changed 4 years ago by
 Commit changed from a0aefd8670fda042b00e1730b682eb5d47824627 to ee237be05d51612dc941dca2d1d10f75dcfe63bf
comment:40 Changed 4 years ago by
I hope that this addresses all your concerns.
comment:41 Changed 4 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Yes, it does. Thank you.
comment:42 followup: ↓ 44 Changed 4 years ago by
Finally... I initially started with this ticket thinking "this should only take 1 hour" :)
comment:43 Changed 4 years ago by
Ah, I know that feeling. Although in my case, that has always been a sign I am in for a whole day of programming. :P
comment:44 in reply to: ↑ 42 Changed 4 years ago by
Replying to jdemeyer:
Finally... I initially started with this ticket thinking "this should only take 1 hour" :)
I "love" when that happens. I haven't really followed this closely since it quickly went beyond any understanding I have of the coercion system, but I'm glad it will be fixed.
The next thing to do might be to fix cases like the one I pointed out in #24263 to ensure that the polynomial implementation that's supposed to be being tested is actually the one being tested.
comment:46 Changed 4 years ago by
 Commit changed from ee237be05d51612dc941dca2d1d10f75dcfe63bf to fff5d7e04b5db731f88ffe5c557a8d8914639aa4
comment:47 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:48 followup: ↓ 49 Changed 4 years ago by
Trivial thing, but can we break this output line since it is so long:
ValueError: domain (Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in x over Integer Ring) and codomain (Univariate Polynomial Ring in t over Univariate Polynomial Ring in x over Integer Ring) must have the same functorial construction over their base rings
Otherwise LGTM and you can set a positive review on my behalf.
comment:49 in reply to: ↑ 48 ; followup: ↓ 50 Changed 4 years ago by
Replying to tscrim:
Trivial thing, but can we break this output line since it is so long
Shouldn't the output in doctests match the actual output from the terminal? If the actual output is one long line, shouldn't the doctest reflect that?
If you insist, I will change it though.
comment:50 in reply to: ↑ 49 ; followup: ↓ 51 Changed 4 years ago by
Replying to jdemeyer:
Replying to tscrim:
Trivial thing, but can we break this output line since it is so long
Shouldn't the output in doctests match the actual output from the terminal? If the actual output is one long line, shouldn't the doctest reflect that?
If you insist, I will change it though.
My usually 90 char wide terminal splits it (essentially randomly) and we have the guideline of 80 char/line in documentation. So with that in mind, I was suggesting the most logical places to split that and keep the lines short. If you would rather leave it as one really (really) long line, then I won't insist, but it makes it much more manageable for me and is in the spirit of the rest of Sage's doc. (I would also not oppose a strict 80 char/line cuts as well.)
comment:51 in reply to: ↑ 50 Changed 4 years ago by
Replying to tscrim:
and we have the guideline of 80 char/line in documentation.
In my mind, there is a difference between the different parts of the documentation:
 textual documentation: word wrap as usual
 code in EXAMPLES: follow PEP 8, which means trying to limit the line lengths
 output in EXAMPLES: I think it is best to keep the exact formatting of the output and not randomly wrap lines.
comment:52 Changed 4 years ago by
 Milestone changed from sage8.1 to sage8.2
 Status changed from needs_review to positive_review
The problem is it is so ugly on my screen that I cannot read it at once with my default settings. IMO, there is no benefit in keeping it "exactly" (where I would say that is not completely accurate with how terminals can wrap) in the doc without some breaks (in this case, I think they are logical). Although this is effectively bikeshedding, and I don't care enough to die on this hill.
comment:53 Changed 4 years ago by
 Status changed from positive_review to needs_work
sage t long warnlong 65.5 src/sage/rings/morphism.pyx ********************************************************************** File "src/sage/rings/morphism.pyx", line 361, in sage.rings.morphism Failed example: phi3 = RingHomomorphism_from_base(H, R.hom([x])); phi3 Expected: Ring endomorphism of Univariate Quotient Polynomial Ring in a over Finite Field of size 2 with modulus x^2 + x + 1 Defn: Induced from base ring by Ring endomorphism of Univariate Polynomial Ring in x over Finite Field of size 2 (using NTL) Defn: x > x Got: Ring endomorphism of Univariate Quotient Polynomial Ring in a over Finite Field of size 2 with modulus x^2 + x + 1 Defn: Induced from base ring by Ring endomorphism of Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X) Defn: x > x **********************************************************************
comment:54 Changed 4 years ago by
Jeroen, will you update the output here, or should I do it?
comment:55 Changed 4 years ago by
I forgot about this ticket. If you can update it, please do.
comment:56 Changed 4 years ago by
 Branch changed from u/jdemeyer/allow__generic__polynomialring_implementation to u/tscrim/generic_polynomialring_implementation24264
 Commit changed from fff5d7e04b5db731f88ffe5c557a8d8914639aa4 to ad3118fd940d36b58ca9271e6a2767b2a9413eb8
 Status changed from needs_work to positive_review
Updated.
New commits:
ad3118f  Merge branch 'u/jdemeyer/allow__generic__polynomialring_implementation' of git://trac.sagemath.org/sage into u/tscrim/generic_polynomialring_implementation24264

comment:57 Changed 4 years ago by
 Commit changed from ad3118fd940d36b58ca9271e6a2767b2a9413eb8 to 0efda1be627e00c9ee03bb70900d37663f638470
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
0efda1b  Fixing doctest output in morphism.pyx.

comment:58 Changed 4 years ago by
 Status changed from needs_review to positive_review
Commit, then push. :p
comment:59 Changed 4 years ago by
 Branch changed from u/tscrim/generic_polynomialring_implementation24264 to 0efda1be627e00c9ee03bb70900d37663f638470
 Resolution set to fixed
 Status changed from positive_review to closed
+1