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: sage-9.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:

Status badges

Description (last modified by Kwankyu Lee)

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 Kwankyu Lee

Description: modified (diff)

comment:2 Changed 19 months ago by Kwankyu Lee

Description: modified (diff)

comment:3 Changed 19 months ago by Xavier Caruso

Branch: u/caruso/comparison_hom

comment:4 Changed 19 months ago by Xavier Caruso

Cc: Kwankyu Lee Markus Wageringel Travis Scrimshaw David Roe added
Commit: 0aa509913eea741eeb19d259c53d6062a6bdd97b
Status: newneeds_review

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

comment:5 Changed 19 months ago by Xavier 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:

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 Kwankyu Lee

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 in reply to:  5 Changed 19 months ago by Kwankyu Lee

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 git

Commit: 0aa509913eea741eeb19d259c53d6062a6bdd97bb4b15013a0232916b498f99bb2ba4adc84aa2a0e

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

c8f66b9generic implementation of rich comparison in the class Morphism
b4b1501implement is_identity and is_coercion_map

comment:9 Changed 19 months ago by Xavier 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 and Morphism. At first, I thought that the latter was reserved for mappings preserving some structure whereas the former was used for set-theoretical mappings. But it doesn't seem to be that obvious: for instance, RingMap (which is explicitly defined as the set of set-theoretic maps between rings in the documentation) derives from Morphism and not from Map. Is this a bug or is there some subtlely behind it?

Last edited 19 months ago by Xavier Caruso (previous) (diff)

comment:10 in reply to:  9 Changed 19 months ago by Kwankyu Lee

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 and Morphism. At first, I thought that the latter was reserved for mappings preserving some structure whereas the former was used for set-theoretical mappings. But it doesn't seem to be that obvious: for instance, RingMap (which is explicitly defined as the set of set-theoretic maps between rings in the documentation) derives from Morphism and not from Map. Is this a bug or is there some subtlely behind it?

RingMap is there just to provide the common name "Set-theoretic ring". I think the adjective "set-theoretic" is meaningless as all ring morphisms are set-theoretic. I guess RingMap could equally be RingMorphism but the author seems to have preferred RingMap as the class name.

comment:11 Changed 19 months ago by Xavier Caruso

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.

Last edited 19 months ago by Xavier Caruso (previous) (diff)

comment:12 in reply to:  11 Changed 19 months ago by Travis Scrimshaw

Replying to caruso:

However, I'm not sure there is a real interest to distinguish between RingMap and just Map.

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 Xavier Caruso

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.

Last edited 19 months ago by Xavier Caruso (previous) (diff)

comment:14 Changed 19 months ago by Xavier Caruso

An additional remark I just noticed: related questions were already discussed in #23204.

comment:15 Changed 19 months ago by Travis Scrimshaw

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 fast-as-possible 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 in reply to:  15 ; Changed 19 months ago by Xavier Caruso

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 fast-as-possible 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.

Last edited 19 months ago by Xavier Caruso (previous) (diff)

comment:17 in reply to:  16 Changed 19 months ago by Travis Scrimshaw

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 Travis Scrimshaw

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 git

Commit: b4b15013a0232916b498f99bb2ba4adc84aa2a0e2eaab5e5976c125739a56e3abc4e9f9d4591076f

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

2eaab5eminor fixes

comment:20 Changed 19 months ago by Xavier Caruso

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 git

Commit: 2eaab5e5976c125739a56e3abc4e9f9d4591076fc989d1e36fd166ae5df91669da02fdf670ca518c

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

c989d1efix doctest

comment:22 Changed 19 months ago by git

Commit: c989d1e36fd166ae5df91669da02fdf670ca518c01736aac202b9d456485b1a401d04a89f7eff833

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

01736aamore typos

comment:23 Changed 19 months ago by git

Commit: 01736aac202b9d456485b1a401d04a89f7eff833c9547e6dace9f9d2e2ff8279ee4882c12213c4aa

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

c9547e6handle the case where base_ring is not defined (or is None)

comment:24 Changed 19 months ago by Xavier Caruso

OK, patchbot now looks happy with the ticket.

So, I'd say that the ticket is ready for review.

comment:25 Changed 19 months ago by Travis Scrimshaw

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 git

Commit: c9547e6dace9f9d2e2ff8279ee4882c12213c4aa80012e6b13405fc460337fde02c59c9a73874de4

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

80012e6factor code in is_identity / is_coercion_map

comment:27 in reply to:  25 Changed 19 months ago by Xavier Caruso

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

You're right. I made the modifications.

comment:28 Changed 19 months ago by Travis Scrimshaw

Status: needs_reviewpositive_review

Then let it be so.

comment:29 Changed 18 months ago by Kwankyu Lee

Status: positive_reviewneeds_work

Merge conflict with latest beta.

comment:30 Changed 16 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:31 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:32 Changed 7 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:33 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.