Remove RingHomomorphism_coercion

[saraedum]

we should try to use .coerce_map_from() instead, so we get is_injective()/is_surjective() and friends right for Hom.natural_map().

Depends on #23184
Depends on #23211

CC: @xcaruso

Component: commutative algebra

Keywords: sd86.5, sd87

Author: David Roe, Julian Rüth

Branch/Commit: 382e2d1

Reviewer: Travis Scrimshaw, Aly Deines, William Stein

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

[roed314]

Changed dependencies from #23184 to #23184, #23211

[roed314]

Branch: u/roed/remove_ringhomomorphism_coercion

[saraedum]

Changed branch from u/roed/remove_ringhomomorphism_coercion to u/saraedum/remove_ringhomomorphism_coercion

[roed314]

Changed branch from u/saraedum/remove_ringhomomorphism_coercion to u/roed/remove_ringhomomorphism_coercion

[sagetrac-git]

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

2043ff3

Fixing doctest errors

[sagetrac-git]

Commit: 2043ff3

[saraedum]

Changed branch from u/roed/remove_ringhomomorphism_coercion to u/saraedum/remove_ringhomomorphism_coercion

[saraedum]

Work Issues: nonzero and is_zero should work like before

[sagetrac-git]

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

d7eb179	Remove RingHomomorphism_coercion
dbd5b0d	fix morphism printing in doctests
f606020	Fixed some doctests

[sagetrac-git]

Changed commit from 2043ff3 to f606020

[sagetrac-git]

Changed commit from f606020 to db5cee6

[sagetrac-git]

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

db5cee6

implement zero() for ring homsets

[sagetrac-git]

Changed commit from db5cee6 to a42ebcf

[sagetrac-git]

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

a42ebcf

implement `__nonzero__` when there is no zero element

[saraedum]

New commits:

a42ebcf

implement `__nonzero__` when there is no zero element

---

New commits:

a42ebcf

implement `__nonzero__` when there is no zero element

[saraedum]

Changed work issues from nonzero and is_zero should work like before to check that nonzero does not cause a major speed regression

[roed314]

Changed keywords from sd86.5 to sd86.5, sd87

[saraedum]

comment:13

The speed regression is minimal. About 235ns vs 220ns in some constructed cases. It should not have much of an effect since most elements overwrite __nonzero__ anyway.

[saraedum]

Changed work issues from check that nonzero does not cause a major speed regression to none

[sagetrac-xander-faber]

comment:16

Doctests are failing in structure/element.pyx, rings/homset.py, combinat/combinat.py, and rings/fraction_field.FpT.pyx. This has to do with the Element.__nonzero__() method producing behavior that disagrees with its docstring. I am addressing this currently.

[tscrim]

comment:17

A strong -1 on calling the category (first): this is relatively expensive, not likely able to be implemented by the MorphismMethods of a category if you have to do formal compositions, and is meant to be overwritten. Really, if you want composite maps, then you should overwrite the _composition_ hook.

No bare exceptions.

I don't understand why this needs to be a more generic class:

diff --git a/src/sage/rings/morphism.pxd b/src/sage/rings/morphism.pxd
index a751a23..26fbeed 100644
--- a/src/sage/rings/morphism.pxd
+++ b/src/sage/rings/morphism.pxd
@@ -15,10 +15,7 @@ cdef class RingMap_lift(RingMap):
     cdef CategoryObject S
 
 cdef class RingHomomorphism(RingMap):
-    cdef RingMap _lift
-
-cdef class RingHomomorphism_coercion(RingHomomorphism):
-    pass
+    cdef Morphism _lift
 
 cdef class RingHomomorphism_im_gens(RingHomomorphism):
     cdef __im_gens

This is almost certainly a speed regression:

diff --git a/src/sage/rings/morphism.pyx b/src/sage/rings/morphism.pyx
index 978fe44..054aea3 100644
--- a/src/sage/rings/morphism.pyx
+++ b/src/sage/rings/morphism.pyx
@@ -373,7 +375,10 @@ def is_RingHomomorphism(phi):
         sage: sage.rings.morphism.is_RingHomomorphism(2/3)
         False
     """
-    return isinstance(phi, RingHomomorphism)
+    # We use the category framework to determine whether something is a ring homomorphism.
+    from sage.categories.map import Map
+    from sage.categories.all import Rings
+    return isinstance(phi, Map) and phi.category_for().is_subcategory(Rings())
 
 cdef class RingMap(Morphism):
     """

This may not be so important as it may not really be used in time-critical code, but it shows up all over the schemes stuff (which should be replaced with a direct isinstance call as they know the morphisms being construction are a subclass of RingHomomorphism). I understand why this is natural, but I don't think this should be done (here) as it is a true behavior change, the is_* functions use are discouraged for trivial cases, and the the above.

I am a little wary of removing RingHomomorphism.__nonzero__ as that specialized code does do a check that could be faster and might be a little better behaved because no equality checking is involved. I just want to make sure you really checked this doesn't introduce a speed regression and works well for inexact rings (which may not be fully doctested).

Why is this change done:

diff --git a/src/sage/schemes/generic/morphism.py b/src/sage/schemes/generic/morphism.py
index 777e3ba..8b7aa8c 100644
--- a/src/sage/schemes/generic/morphism.py
+++ b/src/sage/schemes/generic/morphism.py
@@ -1442,7 +1441,7 @@ class SchemeMorphism_polynomial(SchemeMorphism):
             S = self.codomain().change_ring(R)
             H = Hom(T,S)
 
-        if isinstance(R, Morphism):
+        if isinstance(R, Map):
             if R.domain() == self.base_ring():
                 R = self.domain().ambient_space().coordinate_ring().hom(R, T.ambient_space().coordinate_ring())
         G = []

It does not immediately seem to be related to this ticket.

You need to properly handle old pickles with the old class.

Error messages are not really sentences (according to Python's conventions):

-raise TypeError("Natural coercion morphism from %s to %s not defined."%(self.domain(), self.codomain()))
+raise TypeError("natural coercion morphism from %s to %s not defined"%(self.domain(), self.codomain()))

This change really makes me worry:

@@ -737,11 +715,18 @@ cdef class RingHomomorphism(RingMap):
             sage: f = R.hom([a+b,a-b])
             sage: g = S.hom(Frac(S))
             sage: g*f # indirect doctest
-            Ring morphism:
+            Composite map:
               From: Multivariate Polynomial Ring in x, y over Rational Field
               To:   Fraction Field of Multivariate Polynomial Ring in a, b over Rational Field
-              Defn: x |--> a + b
-                    y |--> a - b
+              Defn:   Ring morphism:
+                      From: Multivariate Polynomial Ring in x, y over Rational Field
+                      To:   Multivariate Polynomial Ring in a, b over Rational Field
+                      Defn: x |--> a + b
+                            y |--> a - b
+                    then
+                      Conversion via FractionFieldElement map:
+                      From: Multivariate Polynomial Ring in a, b over Rational Field
+                      To:   Fraction Field of Multivariate Polynomial Ring in a, b over Rational Field
 
         When ``right`` is defined by the images of generators, the
         result has the type of a homomorphism between its domain and

In particular, it seems like you will now get coercion morphisms that are compositions, which seems to be different behavior than before. This could have subtle effects on code and likely have a performance regression.

I agree with the purpose of this ticket and would like to see the ring morphism code simplified. However, I care a lot about the speed in here because polynomials are a core part of the Sage functionality.

[tscrim]

Work Issues: docbuild

[saraedum]

comment:63

Replying to @tscrim:

I still strongly disagree with adding the check to up the category MRO in the generic FormalCompositeMap for a few special cases. Compare:

sage: V1 = QQ^2
sage: V2 = QQ^3
sage: phi1 = (QQ^1).hom(Matrix([[1, 1]]), V1)
sage: phi2 = V1.hom(Matrix([[1, 2, 3], [4, 5, 6]]), V2)
sage: from sage.categories.map import FormalCompositeMap
sage: c1 = FormalCompositeMap(Hom(QQ^1, V2, phi1.category_for()), phi1, phi2)
sage: %timeit c1.is_injective()
The slowest run took 3132.19 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 41.9 µs per loop
sage: %timeit for _ in range(1000): c1.is_injective()
10 loops, best of 3: 40.8 ms per loop

vs before:

sage: %timeit c1.is_injective()
The slowest run took 34968.62 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 4.88 µs per loop
sage: %timeit for _ in range(1000): c1.is_injective()
100 loops, best of 3: 4.98 ms per loop

That is a 10x slowdown for checking if injectivity/surjectivity is done at the category level, and I believe that most categories will not be able to implement either. At least the only one given so far is injectivity for Fields.

Feel free to try the generic code first and ask the category only if that fails/throws. Then again, when the category can answer it, it's probably faster…Anyway, I just want is_injective to work. I personally do not care about a few µs in is_injective since it currently almost always throws a NotImplementedError for me anyway.

PS: I could also imagine that some categories could quickly answer False when there are dimension reasons why a morphism can not be injective/surjective.

[tscrim]

comment:64

It still will work when you remove the call up to the category in FormalCompositeMap. However, in those cases, the FormalCompositeMap should still return the answer fairly quickly unless you have a long chain to test.

[sagetrac-git]

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

382e2d1

fix docbuild

[sagetrac-git]

Changed commit from d5affa7 to 382e2d1

[saraedum]

comment:66

Let's see if this fixes the docbuild. I am running tests right now. I also created a followup to improve the performance of is_injective/is_surjective #23513.

[saraedum]

Changed work issues from docbuild to none

[saraedum]

comment:68

All long tests pass. Documentation builds.

[williamstein]

comment:69

Hi,

There’s a lot of commits and discussion above. However, it seems to me that the entire point of this ticket is to remove some ugly code that David Roe wrote in 2007 when he was Cythonizing my morphisms code. The relevant git blame is:

03eb48258ab src/sage/rings/morphism.pyx (William Stein     2009-04-11 16:28:50 -0700  901)         return self._lift(x)
^a4928b0cf4 src/sage/rings/morphism.py  (tornaria          2006-02-11 01:13:08 +0000  902)
1d3fa4a1bbb src/sage/rings/morphism.pyx (David Roe         2007-10-05 04:10:04 -0400  903) cdef class RingHomomorphism_coercion(RingHomomorphism):
8093d7d53d0 src/sage/rings/morphism.pyx (David Roe         2007-11-11 21:53:35 +0000  904)     def __init__(self, parent, check = True):
03eb48258ab src/sage/rings/morphism.pyx (William Stein     2009-04-11 16:28:50 -0700  905)         """
4b97d1d434c src/sage/rings/morphism.pyx (Travis Scrimshaw  2012-11-04 11:16:05 -0800  906)         Initialize ``self``.
4b97d1d434c src/sage/rings/morphism.pyx (Travis Scrimshaw  2012-11-04 11:16:05 -0800  907)
03eb48258ab src/sage/rings/morphism.pyx (William Stein     2009-04-11 16:28:50 -0700  908)         INPUT:
4b97d1d434c src/sage/rings/morphism.pyx (Travis Scrimshaw  2012-11-04 11:16:05 -0800  909)
4b97d1d434c src/sage/rings/morphism.pyx (Travis Scrimshaw  2012-11-04 11:16:05 -0800  910)         - ``parent`` -- ring homset
4b97d1d434c src/sage/rings/morphism.pyx (Travis Scrimshaw  2012-11-04 11:16:05 -0800  911)
4b97d1d434c src/sage/rings/morphism.pyx (Travis Scrimshaw  2012-11-04 11:16:05 -0800  912)         - ``check`` -- bool (default: ``True``)
03eb48258ab src/sage/rings/morphism.pyx (William Stein     2009-04-11 16:28:50 -0700  913)
03eb48258ab src/sage/rings/morphism.pyx (William Stein     2009-04-11 16:28:50 -0700  914)         EXAMPLES::
03eb48258ab src/sage/rings/morphism.pyx (William Stein     2009-04-11 16:28:50 -0700  915)
03eb48258ab src/sage/rings/morphism.pyx (William Stein     2009-04-11 16:28:50 -0700  916)             sage: f = ZZ.hom(QQ); f                    # indirect doctes
t
03eb48258ab src/sage/rings/morphism.pyx (William Stein     2009-04-11 16:28:50 -0700  917)             Ring Coercion morphism:
03eb48258ab src/sage/rings/morphism.pyx (William Stein     2009-04-11 16:28:50 -0700  918)               From: Int

They did the hard work to fix all the doctests, everything passes, and the speed regression has no real impact on other code (you can just compare to None), and there is a followup ticket for that. The modified code seems much cleaner. I’m giving this a positive review.

I’ve always thought our coercion code is too complicated/ugly, so anything that cleans it up – and this surely does – is worth it. Please start discussing ideas for optimization on #23513.

(Travis – I’m sitting here talking with the authors of this code, so maybe have more context than you.)

[saraedum]

Changed reviewer from Travis Scrimshaw, Aly Deines to Travis Scrimshaw, Aly Deines, William Stein

[tscrim]

comment:71

I apologize in advance for any frustration in my response. I tried to make it as constructive as I can.

If you really think that this regression in the rest of Sage is worth the speed increase for rings (to which is only benefits certain rings and there is a check to see if the ring is in Fields, which can be expensive), then leave it as a positive review. I'm not going to

Replying to @williamstein:

There’s a lot of commits and discussion above. However, it seems to me that the entire point of this ticket is to remove some ugly code that David Roe wrote in 2007 when he was Cythonizing my morphisms code. The relevant git blame is:

[snip]

They did the hard work to fix all the doctests, everything passes,

I think this alone does not merit a positive review.

and the speed regression has no real impact on other code (you can just compare to None), and there is a followup ticket for that.

That is not true. Checking in/surjectivity for a formal composite morphism that is not in the category of rings will be slowed down by a 10x factor as demonstrated above, and it is not simply comparing something to None. However, I am not fully convinced that the new code results in a speedup:

sage: K.<x> = FunctionField(QQ)
sage: L.<y> = FunctionField(QQ)
sage: M.<z> = FunctionField(QQ)
sage: f = K.hom([y])
sage: g = L.hom([z])
sage: %timeit (g*f).is_injective()
10000 loops, best of 3: 81.3 µs per loop

vs before

sage: %timeit (g*f).is_injective()
10000 loops, best of 3: 46 µs per loop

The reason why I am unsure is because the first time I run with the new code, I get ~28.5 µs. However, this does not happen on re-trails. Do you also experience this? Actually, when I removed the caching on is_injective in Rings() (for testing purposes, which is fair since this would most likely get called repeatedly on new maps if done in a tight loop), I consistently get the faster time and

sage: %timeit phi.is_injective()
The slowest run took 16.17 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 9.33 µs per loop

vs old:

sage: %timeit phi.is_injective()
The slowest run took 6.60 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 19.8 µs per loop

So this does in fact net a ~2x speedup for this case.

However, given the check for if something is in fields, that made me think of the following situation. Suppose we implement a special morphism for ring morphisms out of Z/nZ that checks for injectivity by looking at the image of 1 and the characteristic of the codomain (at least this seems like a reasonable thing to do at some point). Then compose this with some other map that knows about its injectivity (maybe checking if some sort of representation is faithful over various characteristics). With the proposed change, it would require computing the primality of n and not take advantage of the specialized code at all, resulting in a major slowdown with no clear way around other than reimplementing FormalCompositeMap.

Well, this argument is moot if we put the check for Fields() last, but the general principle holds. Some/all of the maps are specialized, but it tries the generic code that can be very expensive (maybe getting the cardinality requires iterating over the entire (large) object, but it is free as an R-module).

The modified code seems much cleaner. I’m giving this a positive review.

The git blame above is not that relevant to the code I am referring to in FormalCompositeMorphism. That added code is the only issue that I (currently) have with this ticket.

What about my comment about undoing the deprecation on is_RingHomomorphism?

I can think of some cases where not having the FormalCompositeMap call up to the category results in errors being raised that otherwise would not. Specifically, if one of the maps in the formal composition being something that cannot say anything. So it is good to have it in there, but I strongly believe it should not be called first. Instead, it should be the fallback.

I’ve always thought our coercion code is too complicated/ugly, so anything that cleans it up – and this surely does – is worth it. Please start discussing ideas for optimization on #23513.

I agree that removing the RingHomomorphism_coercion does simplify the coercion code. However, my objection is to the code added to FormalCompositeMap, which makes things more complicated IMO. I can at least hack around it when I do need the speed. I do not work only with objects in Rings() but can formally compose morphisms. Really, there is no way around this regression other than not having these checks up through the category first.

(Travis – I’m sitting here talking with the authors of this code, so maybe have more context than you.)

I am not. Also, anybody trying to understand why this change was made latter will not have this context either. Since a few people in a room are making decisions and not giving me this context, I am going to stop reviewing and writing any code involving ring morphisms/coercions. I've spent too much time, energy, and political capital working on this.

[williamstein]

comment:72

I am going to stop reviewing and writing any code involving ring morphisms/coercions.

Bummer. Hopefully, you can focus more on the millions of other interesting things you’ve done.

I've spent too much time, energy, and political capital working on this.

For what it is worth, I greatly respect and appreciation your many contributions to Sage, and your careful feedback related to this and many other ticket. Looking forward to seeing you sometime in the future at a Sage days...

[tscrim]

comment:73

Replying to @williamstein:

I've spent too much time, energy, and political capital working on this.

For what it is worth, I greatly respect and appreciation your many contributions to Sage, and your careful feedback related to this and many other ticket. Looking forward to seeing you sometime in the future at a Sage days...

It is worth quite a bit, thank you. It will be nice to see you again too at a future Sage days.

Also thank you to everyone else who worked on this ticket. I do think it is overall a step in the right direction.

[vbraun]

Changed branch from u/saraedum/remove_ringhomomorphism_coercion to 382e2d1