Opened 19 months ago
Last modified 3 months ago
#31783 needs_work defect
Comparison of morphisms is not reliable and may give wrong answers
Reported by:  Kwankyu Lee  Owned by:  

Priority:  major  Milestone:  sage9.8 
Component:  algebra  Keywords:  
Cc:  Kwankyu Lee, Markus Wageringel, Travis Scrimshaw, David Roe  Merged in:  
Authors:  Xavier Caruso  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  u/caruso/comparison_hom (Commits, GitHub, GitLab)  Commit:  80012e6b13405fc460337fde02c59c9a73874de4 
Dependencies:  Stopgaps: 
Description (last modified by )
The current generic implementation of _richcmp_
of morphisms relies on certain assumptions that does not hold in general, and may give mathematically wrong answers. For example,
sage: S.<a,b> = QQ['a,b'].quotient('a*b') sage: R.<x> = S[] sage: f = R.hom([b], R) sage: g = R.hom([b], R) * R.hom(S.hom([a, b], S), R) sage: f == g # should be False True
The aim of this ticket is to reimplement or refactor morphism infrastructure to make comparison of morphisms robust.
This is a sequel to #28617.
Comment of Markus:
It may be necessary to separate the implementations for rings and modules. For rings, it is enough to check that f and g agree on the generators of the ring and, recursively, on the generators of the base ring. For modules, I am not so sure – maybe we need to restrict to the case of module homomorphisms and raise a
NotImplementedError
otherwise.
Change History (33)
comment:1 Changed 19 months ago by
Description:  modified (diff) 

comment:2 Changed 19 months ago by
Description:  modified (diff) 

comment:3 Changed 19 months ago by
Branch:  → u/caruso/comparison_hom 

comment:4 Changed 19 months ago by
Cc:  Kwankyu Lee Markus Wageringel Travis Scrimshaw David Roe added 

Commit:  → 0aa509913eea741eeb19d259c53d6062a6bdd97b 
Status:  new → needs_review 
comment:5 followup: 7 Changed 19 months ago by
Well, maybe the class RingHomomorphism
is not the right place to add this code since I realized that a lot of ring homomorphisms do not derive for this class. Here are a few examples:
sage: from sage.rings.morphism import RingHomomorphism sage: isinstance(ZZ.hom(Zmod(6)), RingHomomorphism) False sage: R.<x> = ZZ[] sage: isinstance(R.coerce_map_from(ZZ), RingHomomorphism) False
Should we change this? Or put the comparison code at the level of categories? Other ideas?
comment:6 Changed 19 months ago by
With the following, this also fixes the problem of #28617, which is really about ring homomorphisms.
 def _richcmp_(self, other, int op): + cpdef _richcmp_(self, other, int op): r""" Compare this ring morphism with ``other``.  This is the generic implementation:  we check if both morphisms agree on the generators of the  domain (including generators of successive base rings). + This is a generic implementation. We check if both morphisms agree on + the generators of the domain, including generators of successive base + rings. TESTS:
comment:7 Changed 19 months ago by
Replying to caruso:
Well, maybe the class
RingHomomorphism
is not the right place to add this code since I realized that a lot of ring homomorphisms do not derive for this class. Here are a few examples:
I think it is the right place. Other ring homomorphisms may gradually(later) move to the RingHomomorphism
class.
comment:8 Changed 19 months ago by
Commit:  0aa509913eea741eeb19d259c53d6062a6bdd97b → b4b15013a0232916b498f99bb2ba4adc84aa2a0e 

comment:9 followup: 10 Changed 19 months ago by
The logic in the class hierarchy of morphisms is sometimes a bit strange (at least I don't always understand it).
In particular, I cannot understand the difference between the classes Map
and Morphism
. At first, I thought that the latter was reserved for mappings preserving some structure whereas the former was used for settheoretical mappings. But it doesn't seem to be that obvious: for instance, RingMap
(which is explicitly defined as the set of settheoretic maps between rings in the documentation) derives from Morphism
and not from Map
. Is this a bug or is there some subtlely behind it?
comment:10 Changed 19 months ago by
Replying to caruso:
The logic in the class hierarchy of morphisms is sometimes a bit strange (at least I don't always understand it).
In particular, I cannot understand the difference between the classes
Map
andMorphism
. At first, I thought that the latter was reserved for mappings preserving some structure whereas the former was used for settheoretical mappings. But it doesn't seem to be that obvious: for instance,RingMap
(which is explicitly defined as the set of settheoretic maps between rings in the documentation) derives fromMorphism
and not fromMap
. Is this a bug or is there some subtlely behind it?
RingMap
is there just to provide the common name "Settheoretic ring". I think the adjective "settheoretic" is meaningless as all ring morphisms are settheoretic. I guess RingMap
could equally be RingMorphism
but the author seems to have preferred RingMap
as the class name.
comment:11 followup: 12 Changed 19 months ago by
Both RingMap
and RingHomomorphism
exist. Reading the documentation, I've understood that RingMap
should be used for morphism between rings which are not ring homomorphisms (a typical example is the map GF(p) > ZZ
taking an integer mod p to its smallest representative).
However, I'm not sure there is a real interest to distinguish between RingMap
and just Map
.
comment:12 Changed 19 months ago by
Replying to caruso:
However, I'm not sure there is a real interest to distinguish between
RingMap
and justMap
.
There could be a performance reason for it as we really want some important rings to have really fast maps (but not necessarily morphisms) between them. I don't know of an explicit example of this, but this might be a reason. Another is that it is just old code that is in need of cleanup.
comment:13 Changed 19 months ago by
I had a discussion with David Roe on zulip about this ticket.
The starting point of our discussion is the observation that there are currently two concurrent systems for handling the different types of morphisms provided by Sage: the class hierarchy and the category framework. This causes confusion and sometimes contradiction.
We believe that it would be great to clarify the situation and clearly separate the roles of these two systems. Roughly speaking, our proposal is to use the class hierarchy to handle different types of implementations and let the category stuff handle mathematical properties of the morphisms.
In this perspective, we do not want to keep the class RingHomomorphism
for instance, but want to move the methods therein to the category. Contrarily having special classes for coercion maps or for maps whose domains are polynomial rings continues to make sense.
Any class can implement its own _richcmp_
method if there is a good reason for (typically a very simple way to compare morphisms of this type). However, a _richcmp_
method should be also provided by the category and it will be used as a fallback if the class does not provide any specific implementation (or if it returns NotImplemented
). (Maybe it would be a good idea to have different names for those methods, e.g. _richcmp_class
and _richcmp_category
, especially since inheritence with the special method _richcmp_
seems to work very bizarrely.)
The same approach could also be used for compositions.
Since this touches a lot of things in the structure of morphisms in Sage, I would appreciate to have your feedback before starting to write code.
comment:14 Changed 19 months ago by
An additional remark I just noticed: related questions were already discussed in #23204.
comment:15 followup: 16 Changed 19 months ago by
Short version, see comment:12.
Long version, overall, I think this would be a great thing to do, but there are a few things to be very careful about in terms of speed regressions. Examples of some rings that should have fastaspossible maps are polynomial rings and finite fields. Granted, comparing morphism is unlikely to be a bottleneck, but if the whole hierarchy is being redone, some of the methods might get swept up in this as well.
One sticking point could be that it is very hard to implement generic comparisons at the category level because these comparisons depend strongly on the specific implementation of the morphisms. There is the related issue with the homset parents not having a unique element class as you can want morphisms that behave very differently or needing varying internal structures.
Note that _richcmp_
is not a special method (as opposed to __richcmp__
); it follows the usual inheritance. However, many of the morphisms are extension classes, so these actual morphism instances are not dynamically created classes and some magic needs to be done with __getattr__
in order to check stuff in the category.
My suggestion would be to map out a little bit about the class and category hierarchy that you want to have with the morphisms for the rings. It doesn't need to be complete, but having a bit of a plan before starting to code could be useful.
comment:16 followup: 17 Changed 19 months ago by
Replying to tscrim:
Short version, see comment:12.
Oh yes, I saw your comment but forgot to answer.
Since basically the class RingMap
does nothing more than Map
except redefining _repr_type
, I can't believe there is a performance issue here.
But I agree with you that in general we have to be very careful about this.
Long version, overall, I think this would be a great thing to do, but there are a few things to be very careful about in terms of speed regressions. Examples of some rings that should have fastaspossible maps are polynomial rings and finite fields. Granted, comparing morphism is unlikely to be a bottleneck, but if the whole hierarchy is being redone, some of the methods might get swept up in this as well.
That's a good point. Especially since I've understood (but I might be wrong) that it's not possible to have cython methods in the category. Is this correct?
One sticking point could be that it is very hard to implement generic comparisons at the category level because these comparisons depend strongly on the specific implementation of the morphisms. There is the related issue with the homset parents not having a unique element class as you can want morphisms that behave very differently or needing varying internal structures.
I think it makes sense at least for some categories. For instance, equalities of ring homomorphisms can be checked by comparing the images of the generators. Again, I might be wrong but I suspect that in most cases, the objects in Sage are finitely generated, so if we have enough information about the underlying structure (which is a priori encoded in the category), implementing a reliable comparison test sounds feasible.
Note that
_richcmp_
is not a special method (as opposed to__richcmp__
); it follows the usual inheritance. However, many of the morphisms are extension classes, so these actual morphism instances are not dynamically created classes and some magic needs to be done with__getattr__
in order to check stuff in the category.
OK. Thanks for the clarification.
I previously encountered several issues with inheritance of rich comparisons, but it was probably because I was using directly __richcmp__
.
My suggestion would be to map out a little bit about the class and category hierarchy that you want to have with the morphisms for the rings. It doesn't need to be complete, but having a bit of a plan before starting to code could be useful.
That's a good idea. Thanks.
comment:17 Changed 19 months ago by
Replying to caruso:
Especially since I've understood (but I might be wrong) that it's not possible to have cython methods in the category. Is this correct?
Yes, that's correct since categories have to by in Python (IIRC, I think there is a limitation with how things get converted into Cython. Much more certainly, categories cannot be extension classes.)
comment:18 Changed 19 months ago by
Are you going to do this restructuring for this ticket or on a followup ticket?
One change for this ticket:
Implemented only when the domain has methods `gens` and `base_ring`. +Implemented only when the domain has methods ``gens`` and ``base_ring``.
Before the patchbot will run, the ticket needs an author.
comment:19 Changed 19 months ago by
Commit:  b4b15013a0232916b498f99bb2ba4adc84aa2a0e → 2eaab5e5976c125739a56e3abc4e9f9d4591076f 

Branch pushed to git repo; I updated commit sha1. New commits:
2eaab5e  minor fixes

comment:20 Changed 19 months ago by
Authors:  → Xavier Caruso 

My initial plan was to put all the changes in this ticket but, thinking again at it, I think you're right, it's better to open a new ticket.
comment:21 Changed 19 months ago by
Commit:  2eaab5e5976c125739a56e3abc4e9f9d4591076f → c989d1e36fd166ae5df91669da02fdf670ca518c 

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

comment:22 Changed 19 months ago by
Commit:  c989d1e36fd166ae5df91669da02fdf670ca518c → 01736aac202b9d456485b1a401d04a89f7eff833 

Branch pushed to git repo; I updated commit sha1. New commits:
01736aa  more typos

comment:23 Changed 19 months ago by
Commit:  01736aac202b9d456485b1a401d04a89f7eff833 → c9547e6dace9f9d2e2ff8279ee4882c12213c4aa 

Branch pushed to git repo; I updated commit sha1. New commits:
c9547e6  handle the case where base_ring is not defined (or is None)

comment:24 Changed 19 months ago by
OK, patchbot now looks happy with the ticket.
So, I'd say that the ticket is ready for review.
comment:25 followup: 27 Changed 19 months ago by
Reviewers:  → Travis Scrimshaw 

This seems good to me overall. I don't immediately see the need for the is_coercion_map()
method. Yet, that could benefit from having a quick check to see if self is
the coercion map:
 if not self.codomain().has_coerce_map_from(domain): + f = self.codomain()._internal_coerce_map_from(domain) + if f is None: return False + if f is self: + return True
Also, there is a bunch of duplicate code with is_coercion_map()
and is_identity()
. I think is_identity()
can simply call is_coercion_map()
after checking the domain equals the codomain.
comment:26 Changed 19 months ago by
Commit:  c9547e6dace9f9d2e2ff8279ee4882c12213c4aa → 80012e6b13405fc460337fde02c59c9a73874de4 

Branch pushed to git repo; I updated commit sha1. New commits:
80012e6  factor code in is_identity / is_coercion_map

comment:27 Changed 19 months ago by
Replying to tscrim:
I don't immediately see the need for the
is_coercion_map()
method.
Well, I don't have any very good reason but I'd say that it's natural to have this method in sage where coercion maps play a central role.
Yet, that could benefit from having a quick check to see if
self is
the coercion map: if not self.codomain().has_coerce_map_from(domain): + f = self.codomain()._internal_coerce_map_from(domain) + if f is None: return False + if f is self: + return TrueAlso, there is a bunch of duplicate code with
is_coercion_map()
andis_identity()
. I thinkis_identity()
can simply callis_coercion_map()
after checking the domain equals the codomain.
You're right. I made the modifications.
comment:29 Changed 18 months ago by
Status:  positive_review → needs_work 

Merge conflict with latest beta.
comment:30 Changed 16 months ago by
Milestone:  sage9.4 → sage9.5 

comment:31 Changed 12 months ago by
Milestone:  sage9.5 → sage9.6 

comment:32 Changed 7 months ago by
Milestone:  sage9.6 → sage9.7 

comment:33 Changed 3 months ago by
Milestone:  sage9.7 → sage9.8 

I set this ticket to "needs review" in order to get feedback from the patchbot.