Opened 9 months ago

Last modified 5 weeks ago

#31783 needs_work defect

Comparison of morphisms is not reliable and may give wrong answers

Reported by: klee Owned by:
Priority: major Milestone: sage-9.6
Component: algebra Keywords:
Cc: klee, gh-mwageringel, tscrim, roed 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 klee)

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 (31)

comment:1 Changed 9 months ago by klee

  • Description modified (diff)

comment:2 Changed 9 months ago by klee

  • Description modified (diff)

comment:3 Changed 9 months ago by caruso

  • Branch set to u/caruso/comparison_hom

comment:4 Changed 9 months ago by caruso

  • Cc klee gh-mwageringel tscrim roed added
  • Commit set to 0aa509913eea741eeb19d259c53d6062a6bdd97b
  • Status changed from new to needs_review

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

comment:5 follow-up: Changed 9 months ago by 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 9 months ago by klee

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 9 months ago by klee

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 9 months ago by git

  • Commit changed from 0aa509913eea741eeb19d259c53d6062a6bdd97b to b4b15013a0232916b498f99bb2ba4adc84aa2a0e

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 follow-up: Changed 9 months ago by 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 9 months ago by caruso (previous) (diff)

comment:10 in reply to: ↑ 9 Changed 9 months ago by klee

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 follow-up: Changed 9 months ago by 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 9 months ago by caruso (previous) (diff)

comment:12 in reply to: ↑ 11 Changed 9 months ago by tscrim

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 8 months ago by 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 8 months ago by caruso (previous) (diff)

comment:14 Changed 8 months ago by caruso

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

comment:15 follow-up: Changed 8 months ago by tscrim

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 ; follow-up: Changed 8 months ago by 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 8 months ago by caruso (previous) (diff)

comment:17 in reply to: ↑ 16 Changed 8 months ago by tscrim

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 8 months ago by tscrim

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 8 months ago by git

  • Commit changed from b4b15013a0232916b498f99bb2ba4adc84aa2a0e to 2eaab5e5976c125739a56e3abc4e9f9d4591076f

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

2eaab5eminor fixes

comment:20 Changed 8 months ago by caruso

  • Authors set to 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 8 months ago by git

  • Commit changed from 2eaab5e5976c125739a56e3abc4e9f9d4591076f to c989d1e36fd166ae5df91669da02fdf670ca518c

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

c989d1efix doctest

comment:22 Changed 8 months ago by git

  • Commit changed from c989d1e36fd166ae5df91669da02fdf670ca518c to 01736aac202b9d456485b1a401d04a89f7eff833

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

01736aamore typos

comment:23 Changed 8 months ago by git

  • Commit changed from 01736aac202b9d456485b1a401d04a89f7eff833 to c9547e6dace9f9d2e2ff8279ee4882c12213c4aa

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 8 months ago by caruso

OK, patchbot now looks happy with the ticket.

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

comment:25 follow-up: Changed 8 months ago by tscrim

  • Reviewers set to 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 8 months ago by git

  • Commit changed from c9547e6dace9f9d2e2ff8279ee4882c12213c4aa to 80012e6b13405fc460337fde02c59c9a73874de4

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 8 months ago by 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 8 months ago by tscrim

  • Status changed from needs_review to positive_review

Then let it be so.

comment:29 Changed 8 months ago by klee

  • Status changed from positive_review to needs_work

Merge conflict with latest beta.

comment:30 Changed 5 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:31 Changed 5 weeks ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6
Note: See TracTickets for help on using tickets.