Allow actions of a parent on itself

[simon-king-jena]

Currently, ModuleElement.__mul__ raises an error when both elements have the same parent. Hence, in order to define a ring structure, one must not start with ModuleElement, which is bad, since sometimes the concrete structure only depends on the category (see CombinatorialFreeModule).

The approach to be implemented here: ModuleElement.__mul__ and RingElement.__mul__ should provide short-cuts in cases where there is an obvious way to be faster than calling the coercion model, and otherwise it is the job of the coercion model (NOT of ModuleElement.__mul__) to complain if the two elements come from the same parent without an action being defined.

Hence, it should be possible to start with ModuleElement and get a ring structure on top of it by an appropriate action of the parent on itself. Here is an example that should be made work:

sage: from sage.categories.action import Action
sage: class RingStructure(Action):
....:     def __init__(self, R):
....:         Action.__init__(self, R, R, True, operator.mul)
....:     def _call_(self, g, a):
....:         return g._mul_(a)
....:     
sage: from sage.structure.element import ModuleElement
sage: class MyElement(ModuleElement):
....:     def __init__(self, P, L):
....:         ModuleElement.__init__(self, P)
....:         self.l = L
....:     def _repr_(self):
....:         return "<{}>".format(self.l)
....:     def _add_(self, other):
....:         return self.parent()(zip(self.l, other.l))
....:     def _mul_(self, other):
....:         return self.parent()(self.l+other.l)
....:     
sage: class MyParent(Parent):
....:     Element = MyElement
....:     def _get_action_(self, S, op, self_on_left):
....:         if S is self and op == operator.mul and self_on_left:
....:             return RingStructure(self)
....:         
sage: P = MyParent(category=Rings())
sage: l1 = P([1,2])
sage: l2 = P([3,4])
sage: l1+l2
<[(1, 3), (2, 4)]>
sage: l1*l2
<[1, 2, 3, 4]>

Moreover, it should be possible to define the actions using ParentMethods in the category framework. I.e., _get_action_ should be moved from Parent to Sets.ParentMethods. This is why #18756 (where the whole idea started) is a dependency.

More precisely: The above RingStructure (perhaps with some sanity test similar to sage.structure.coerce_action.ModuleAction) should be defined in sage.structure.coerce_actions and used by Rings.ParentMethods._get_action_.

Summary

• multiplication can still be defined by category initialisation in Magmas(). However, it should become faster and it should in future be easier to import the multiplication from a fast cython module.
• The way to define an internal multiplication should be more uniform throughout Sage: One simply defines _mul_ and initialises in Magmas(). Overriding __mul__ (which in some situations was still needed) should in future be even more useless.
• Similar statements hold for _add_.

Depends on #18756

CC: @nthiery @sagetrac-sage-combinat

Component: coercion

Keywords: actions on itself

Author: Simon King

Branch/Commit: u/SimonKing/allow_actions_of_parent_on_itself @ d71a456

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

[simon-king-jena]

comment:1

See comment 24 at #18756 for why I think we should have a dependency.

[simon-king-jena]

Dependencies: #18756

[simon-king-jena]

comment:4

More precisely: The example from the ticket description shouldn't be called RingStructure but MagmaStructure, it should be defined in Magmas.ParentMethods._get_action_, and it should have an additive counterpart.

[simon-king-jena]

comment:5

Remark: Magmas.ElementMethods does provide a generic multiplication using _mul_ (when present) and using coercion otherwise.

Two problems: There is an import statement in the multiplication method, which, if I recall correctly, is not for free. And it first checks the presence of a _mul_ attribute, which also slows things down.

So, it would be interesting to see if the following approach yields faster code:

• ALL element classes should have generic __mul__ and __add__ methods. Those of sage.structure.elements.Element will just rely on coercion, whereas ModuleElement and RingElement first try a short-cut via _mul_ resp. _add_. So, the hierarchy of algebraic base classes would be reflected in the usage of shortcuts.
• The proposed actions MagmaStructure and AdditiveMagmaStructure should test the presence of the attributes _mul_ resp. _add_ during initialisation, ONCE. Henceforth, the presence of the attribute does not need to be tested any longer.

So, rather than providing a __mul__ methods, Magmas() would provide an action, and there should be a __mul__ method for Element instead. Really, we need to test and get timings.

[simon-king-jena]

comment:6

I haven't pushed my branch yet. Anyway, what I can do is the following:

sage: class MyElement(Element):
....:     def __init__(self, P, L):
....:         Element.__init__(self, P)
....:         self.l = L
....:     def _repr_(self):
....:         return "<{}>".format(self.l)
....:     def _add_(self, other):
....:         return self.parent()(zip(self.l, other.l))
....:     def _mul_(self, other):
....:         return self.parent()(self.l+other.l)
sage: class MyMElement(ModuleElement):
....:     def __init__(self, P, L):
....:         ModuleElement.__init__(self, P)
....:         self.l = L
....:     def _repr_(self):
....:         return "<{}>".format(self.l)
....:     def _add_(self, other):
....:         return self.parent()(zip(self.l, other.l))
....:     def _mul_(self, other):
....:         return self.parent()(self.l+other.l)
sage: class MyRElement(RingElement):
....:     def __init__(self, P, L):
....:         RingElement.__init__(self, P)
....:         self.l = L
....:     def _repr_(self):
....:         return "<{}>".format(self.l)
....:     def _add_(self, other):
....:         return self.parent()(zip(self.l, other.l))
....:     def _mul_(self, other):
....:         return self.parent()(self.l+other.l)
sage: class MyParent(Parent):
....:     Element = MyElement
sage: class MyMParent(Parent):
....:     Element = MyMElement
sage: class MyRParent(Parent):
....:     Element = MyRElement
sage: P = MyParent(category=Rings())
sage: l = P([1,2])
sage: l*l
<[1, 2, 1, 2]>
sage: PM = MyMParent(category=Rings())
sage: lM = PM([1,2])
sage: lM*lM
<[1, 2, 1, 2]>
sage: PR = MyRParent(category=Rings())
sage: lR = PR([1,2])
sage: lR*lR
<[1, 2, 1, 2]>
sage: %timeit l*l
The slowest run took 4.68 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 8.77 µs per loop
sage: %timeit lM*lM
The slowest run took 6.35 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 7.89 µs per loop
sage: %timeit lR*lR
The slowest run took 7.06 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 7.22 µs per loop

Explanation:

1. In P, we use Element as starting point. It has no __mul__, hence, __mul__ is obtained from some element method of the category of rings.
2. In PM, we use ModuleElement as starting point.
   • It has a __mul__ method that in vanilla Sage would refuse to carry a ring structure. Hence, the above wouldn't work in vanilla Sage. I have changed the coercion framework so that it does not complain about a ring structure.
   • Since it has a __mul__ method, it cannot inherit a ring multiplication from the category element methods. Instead, the parent inherits _get_action_ from category parent methods, as per Use coerce actions in the category framework #18756.
3. This would be the "classical" way to define a ring structure.

As you can see, of course a specialised cythoned __mul__ method for rings is fastest. The first approach is taken in CombinatorialFreeModule, if I understand correctly, and is slowest (not by much, but it is). The new approach to use an action of self on itself somehow is in the middle, speed-wise.

Before I push my branch, I'll see what happens if I provide Element with a default __mul__ method that simply calls the coercion model. It will of course make the first approach impossible, but I guess it would speed-up the second (i.e., new) approach.

[simon-king-jena]

comment:7

Replying to @simon-king-jena:

Before I push my branch, I'll see what happens if I provide Element with a default __mul__ method that simply calls the coercion model. It will of course make the first approach impossible, but I guess it would speed-up the second (i.e., new) approach.

To be clear: It would still be the case that CombinatorialFreeModuleElement would be based on Element, and it would still be the case that it obtains _mul_ (single underscore) from the category, and it would still be the case that it obtains multiplication from the category. The difference is that it does not obtain the multiplication by inheriting a __mul__ (double underscore) method from the category, but by using a coerce action obtained from the category.

In particular, the existing user code will not change.

[simon-king-jena]

comment:8

Replying to @simon-king-jena:

Before I push my branch, I'll see what happens if I provide Element with a default __mul__ method that simply calls the coercion model. It will of course make the first approach impossible, but I guess it would speed-up the second (i.e., new) approach.

This is what happens:

sage: %timeit l*l
The slowest run took 6.49 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 7.71 µs per loop
sage: %timeit lM*lM
The slowest run took 5.82 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 7.91 µs per loop
sage: %timeit lR*lR
The slowest run took 4.27 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 7.03 µs per loop

In other words, using Element becomes faster when defining a ring structure than ModuleElement. Probable reason: The default Element.__mul__ that I am suggesting will immediately use coercion, whereas ModuleElement.__mul__ first tries some shortcut that is not available in my example.

Of course, RingElement.__mul__ is still fastest, as it uses the right shortcut.

Before pushing my branch, I plan to add tests and documentation. The documentation will go to sage.structure.element and sage.structure.parent. However, it is my experience that people using sage.combinat have a tendency to work around coercion (see for example sage.combinat.permutation.Permutation.__mul__).

Can you suggest a place to put documentation on coercion so that it is actually found by sage.combinat users?

[simon-king-jena]

comment:9

I had a look at sage.combinat, and it turns out that the situation is not sooooo bad as I thought.

1. Permutation needs to be sanitised. It inherits from Element. Since here I plan to introduce a default Element.__mul__ using coercion model, Permutation.__mul__ needs to be removed, and instead we need an action. It would be easy to implement, and I bet it is faster.

2. Word does not even inherit from Element, but it mimics the element-parent scheme (by providing a cdef _parent attribute and a parent() method). It should be possible to determine the result of multiplication by looking at the involved parents. Hence:

   • It would be a good idea to implement something like pushouts for families of words. Thus:
   • It would make sense to have a WordFunctor construction functor from Sets() to an appropriate category. The appropriate category could be Monoids() in the case of finite or infinite words, but could be Sets() in the case of "words avoiding 12" and those things (i.e., the product of two pattern avoiding words is not necessarily pattern avoiding).

   Then, one could finally take advantage of Sage's coercion framework for words.

I suggest to sanitise Permutation here, but keep Word for a later ticket.

[simon-king-jena]

comment:10

PS: Having a pushout construction for permutations would also be nice. Again, it would be for a later ticket.

[simon-king-jena]

comment:11

PPS: Is it actually Monoids() in the case of infinite words? I guess one cannot multiply an infinite word with a finite or infinite word. One can only multiply a finite with a finite or infinite word. So, it is "Monoidoids()" (i.e., we have a partial multiplication that is associative when defined and has a unit).

[simon-king-jena]

comment:12

It will not be easy to make my proposed changes work throughout the sage library. There are zillions of errors in sage.modular (I am sure this is because it was previously worked around coercion...). Well, we will see.

[simon-king-jena]

comment:14

With the branch, that I have still not pushed, I get

sage -t src/sage/monoids/free_abelian_monoid.py  # 1 doctest failed
sage -t src/sage/categories/primer.py  # 1 doctest failed
sage -t src/sage/categories/rings.py  # 1 doctest failed
sage -t src/sage/tests/gap_packages.py  # 1 doctest failed
sage -t src/sage/tests/book_schilling_zabrocki_kschur_primer.py  # 2 doctests failed
sage -t src/sage/groups/matrix_gps/group_element.py  # 1 doctest failed
sage -t src/sage/groups/semimonomial_transformations/semimonomial_transformation.pyx  # 1 doctest failed
sage -t src/sage/groups/perm_gps/permgroup_named.py  # 2 doctests failed
sage -t src/sage/sets/finite_set_maps.py  # 3 doctests failed
sage -t src/sage/dev/sagedev.py  # 2 doctests failed
sage -t src/sage/combinat/posets/posets.py  # 1 doctest failed
sage -t src/sage/combinat/sf/sf.py  # 3 doctests failed
sage -t src/sage/combinat/sf/new_kschur.py  # 10 doctests failed
sage -t src/sage/schemes/toric/morphism.py  # 3 doctests failed
sage -t src/sage/geometry/fan_morphism.py  # 6 doctests failed
sage -t src/sage/geometry/hyperplane_arrangement/hyperplane.py  # 1 doctest failed

Not so bad, actually...

[simon-king-jena]

Branch: u/SimonKing/allow_actions_of_parent_on_itself

[simon-king-jena]

Author: Simon King

[simon-king-jena]

Commit: b57a6e3

[simon-king-jena]

comment:16

I have changed the logic in the bin_op() method of the coercion model, so that it is safer against infinite recursion. The error messages in most cases do not just say that the operation "+" is unsupported, but say that a common parent has not been found. Changing the expected error messages is the hardest part of the latest commit.

Most important change: The coercion model now makes actual use of single underscore methods!

You may be surprised by the implied statement that previously the coercion model did not use them. In fact, it didn't. Up to now, the single underscore methods have only been used as short-cuts in RingElement.__mul__ and friends. I have changed it, so that the short-cut still works, but additionally the coercion model explicitly calls the single underscore methods (when available) if both operands belong to the same parent.

[sagetrac-git]

Changed commit from b57a6e3 to d71a456

[sagetrac-git]

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

d71a456

forgotten changes of expected error messages in tests

[simon-king-jena]

comment:18

Here are some timings. The code used:

sage: from sage.structure.element import Element, ModuleElement, RingElement
sage: class MyElement(Element):
....:     def __init__(self, P, L):
....:         Element.__init__(self, P)
....:         self.l = L
....:     def _repr_(self):
....:         return "<{}>".format(self.l)
....:     def _add_(self, other):
....:         return self.parent()(zip(self.l, other.l))
....:     def _mul_(self, other):
....:         return self.parent()(self.l+other.l)
sage: class MyMElement(ModuleElement):
....:     def __init__(self, P, L):
....:         ModuleElement.__init__(self, P)
....:         self.l = L
....:     def _repr_(self):
....:         return "<{}>".format(self.l)
....:     def _add_(self, other):
....:         return self.parent()(zip(self.l, other.l))
....:     def _mul_(self, other):
....:         return self.parent()(self.l+other.l)
sage: class MyRElement(RingElement):
....:     def __init__(self, P, L):
....:         RingElement.__init__(self, P)
....:         self.l = L
....:     def _repr_(self):
....:         return "<{}>".format(self.l)
....:     def _add_(self, other):
....:         return self.parent()(zip(self.l, other.l))
....:     def _mul_(self, other):
....:         return self.parent()(self.l+other.l)
sage: class MyParent(Parent):
....:     Element = MyElement
sage: class MyMParent(Parent):
....:     Element = MyMElement
sage: class MyRParent(Parent):
....:     Element = MyRElement

Here are different settings, where in each case I also compare with vanilla sage-6.8.beta5.

1. Action obtained from the category:

sage: P = MyParent(category=Rings())
sage: l = P([1,2])
sage: %timeit l*l
The slowest run took 64.43 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 7.82 µs per loop  # 8.87 µs in beta5
sage: %timeit l+l
The slowest run took 24.53 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 8.44 µs per loop # 9.49 µs in beta5

2. The coercion model using single underscore methods. Both examples won't work in beta5

sage: P = MyParent(category=Sets())
sage: l = P([1,2])
sage: %timeit l*l
The slowest run took 15.44 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 10.3 µs per loop
sage: %timeit l+l
The slowest run took 11.54 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 10.7 µs per loop

3. ModuleElement using a short-cut for "+" and not complaining about a multiplication action obtained from the category:

sage: P = MyMParent(category=Rings())
sage: l = P([1,2])
sage: %timeit l*l
The slowest run took 108.72 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 7.88 µs per loop  # won't work in beta5
sage: %timeit l+l
The slowest run took 5.98 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 8.05 µs per loop  # 8.01 µs in beta5 (of course no significant change)

4. ModuleElement using a shortcut for "+" and allowing the coercion model to use single underscore methods for "*":

sage: P = MyMParent(category=Sets())
sage: l = P([1,2])
sage: %timeit l*l
The slowest run took 14.45 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 10.7 µs per loop  # won't work in beta5
sage: %timeit l+l
The slowest run took 4.25 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 8.69 µs per loop  # 8.02 µs in beta5. Should actually be the same time! This branch hasn't changed!

5. RingElement using short-cuts for "+" and for "*". Of course there are no significant changes wrt. beta5, as the short-cut didn't change.

sage: P = MyRParent(category=Sets())
sage: l = P([1,2])
sage: %timeit l*l
The slowest run took 4.75 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 7.12 µs per loop  # 7.02 µs with beta5
sage: %timeit l+l
The slowest run took 4.58 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 8.07 µs per loop  # 7.98 µs with beta5

[videlec]

comment:19

Hello,

There are some clear troubles with the patchbot... some elements do not know how to multiply anymore.

Vincent

[simon-king-jena]

comment:20

Also, the doctest coverage is not 100%.

[simon-king-jena]

comment:21

Replying to @videlec:

There are some clear troubles with the patchbot... some elements do not know how to multiply anymore.

In two of the failing tests, it is just the error message that has changed. In the third, it could be that something needs to be done.

[simon-king-jena]

comment:22

If I recall correctly, some people have worked on similar issues. But I am not sure about the ticket numbers. Hence, is what I propose here done already?