#18756: Use cython and coercion for CombinatorialFreeModule
-------------------------------------------------+-------------------------
Reporter: SimonKing | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.8
Component: algebra | Resolution:
Keywords: CombinatorialFreeModule, | Merged in:
cython, coercion | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | Stopgaps:
Dependencies: |
-------------------------------------------------+-------------------------
Comment (by SimonKing):
Replying to [comment:6 nthiery]:
> > - `ELement` uses `_acted_on_/_acted_upon_` to implement actions. It
has no `_lmul_`, which means that the comment "for backward compatibility"
fails entirely.
> > - `ModuleElement` provides the infrastructure for both general actions
(inherited from `Element`) and a special path for scalar multiplication
(`_lmul_/_rmul_`). Problem: You can not implement a ring multiplication
when you just inherit from `ModuleElement`, since `ModuleElement.__mul__`
raises an error if both arguments belong to the same parent.
> > - `RingElement` provides the infrastructure for general actions,
scalar multiplication, and ring multiplication (via `_mul_`).
>
> Yup, the single inheritance of Cython is a very strong constraint. It
> pushes us to do crap.
Perhaps it would really be better to change `ModuleElement.__mul__`? The
fact that it raises an error if both parents are equal is not good. It may
haVe been motivated by an attempt to break an infinite recursion (namely:
To test existence of an action, you would try to multiply elements, but to
multiply elements, you need to know of there is an action). Perhaps that
cycle should be broken in a different way?
> This would make things complicated for subclasses of
> `CombinatorialModule` that have an Element class that inherits from
> `CombinatorialFreeModuleElement`.
Right. In contrast to the category framework, where the element class of a
super-category is mixed in, the `.Element` attribute of a super-class is
not mixed in `:-/`. Perhaps this could be implemented? Perhaps the
`.element_class` lazy attribute could also have a look at
`super(self,type(self)).Element` or so?
> Now a question: what are the speed critical things that we really need
> to be Cythonized? If it's just the `__mul__` methods and friends, it
> would be worth experimenting with replacing their Python
> implementations in the Modules/Rings/Algebras categories by Cythonized
> methods (with recent versions of Cython, this is possible). Maybe this
> would be sufficient.
If I understand the general pattern: To implement an algebraic structure
using `CombinatorialFreeModule`, one implements methods such as
`product_on_basis` or `degree_on_basis`.
I must admit that by searching the code for the past 30 minutes, I did not
really succeed to find out at what place "product_on_basis" is actually
turned into a `__mul__` method for `FreeModuleElement`s. But after
searching 60 minutes, I found:
- `Magmas().element_class` provides a `__mul__` method that mimics the
`__mul__` method of ring elements. Fine, but Python.
- `Magmas().parent_class.__init_extra__` assigns a `_mul_` method for the
element class by setting it to `_mul_parent`
- `_mul_parent` calls `self.parent().product`
- `.product` calls `product_on_basis`.
These are many indirections---too many python calls for a single
multiplication in high performance code, I'd say.
One detail: Apparently, setting `_mul_` to an attribute of the class
results in slower access than what is possible when providing a method
during **creation** of the class (such as `_mul_parent`):
{{{
sage: A = DiGraph({1:{2:['a']}, 2:{3:['b']}, 3:{1:['c'], 4:['m']},
4:{5:['n']}, 5:{6:['x'],7:['y']}, 6:{7:['z']}}).path_semigroup().algebra
(QQ)
sage: A.inject_variables()
Defining e_1, e_2, e_3, e_4, e_5, e_6, e_7, a, b, c, m, n, x, y, z
sage: %timeit x.__mul__
The slowest run took 122.24 times longer than the fastest. This could mean
that an intermediate result is being cached
10000000 loops, best of 3: 50.7 ns per loop
sage: %timeit x._mul_parent
The slowest run took 100.65 times longer than the fastest. This could mean
that an intermediate result is being cached
10000000 loops, best of 3: 61.6 ns per loop
sage: %timeit x._mul_
The slowest run took 41.40 times longer than the fastest. This could mean
that an intermediate result is being cached
10000000 loops, best of 3: 121 ns per loop
}}}
Hence, we would already gain a tiny bit by providing `_mul_` during
creation of the element class, not afterwards.
By the way, why is all this in `Magmas()`? It uses "product_on_basis",
hence, it uses the notion of a basis, which isn't defined for magmas,
right? In fact, I first searched in `AlgebrasWithBasis` to find the
definition of multiplication with `product_on_basis`.
--
Ticket URL: <http://trac.sagemath.org/ticket/18756#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
