Opened 7 years ago

Last modified 5 years ago

#14279 needs_work defect

Coercion for homsets

Reported by: SimonKing Owned by: nthiery
Priority: major Milestone: sage-6.4
Component: categories Keywords:
Cc: Merged in:
Authors: Simon King Reviewers:
Report Upstream: N/A Work issues: documentation
Branch: Commit:
Dependencies: #11490, #14214, #14249, #14225, #14278 Stopgaps:

Description

Homsets are parents that, up to now, do not use Sage's coercion model and do not use element classes. Morphisms are elements that, up to now, would define a custom __mul__ and __add__ and so on.

The purpose of this ticket is to use the new framework. As you can imagine, this involves many changes. One important change: I let sage.categories.map.Map inherit from sage.structure.element.ModuleElement. Not all homsets are modules, of course, but when they are, then one can simply define single underscore _add_, _rmul_ and _composition_ (the latter is for composition of maps) as usual, so that one does not need to overload __mul__ so often.

Another important change: Domain and codomain of a morphism used to be parents, but that's wrong, because parents are CategoryObjects that contain elements, but we can speak of morphisms (purely categorically) without elements. Hence, I changed domain and codomain into CategoryObject.

In sage.homology, no reasonable base classes were used: Everything was directly inheriting from SageObject. I improved this.

While I was at it, I was fixing some homset related pickling problems, and I implemented a cache for a parent where that has been previously tried unsuccessfully.

It is difficult to say what component this ticket belongs to. I try "categories".

Attachments (2)

trac_14279-new_coercion_for_homsets.patch (120.9 KB) - added by SimonKing 7 years ago.
Main patch, needs better documentation of the changes
trac_14279-composition_action.patch (12.9 KB) - added by SimonKing 7 years ago.
Composition action

Download all attachments as: .zip

Change History (9)

Changed 7 years ago by SimonKing

Main patch, needs better documentation of the changes

comment:1 Changed 7 years ago by SimonKing

  • Status changed from new to needs_review

I change it into "needs review", in order to let the patchbot do some work.

However, it will need a second patch, that improves documentation. But I certainly would like to get some input at that point.

Changed 7 years ago by SimonKing

Composition action

comment:2 Changed 7 years ago by SimonKing

I think it makes sense to introduce a new type of action (i.e., a subclass of sage.categories.action.Action) for multiplying maps by composition.

The advantages:

  • Actions are cached. Hence, only when the action is created for the first time, it is needed to check whether the codomain of the right factor matches the domain of the left factor. Currently, this is checked in every single multiplication.
  • Moreover, the action can keep a reference on the homset that contains the composed map, so that there is no need to call the Hom function in every single multiplication.
  • Using actions is, I think, part of using the new coercion model.

The disadvantage:

  • _get_action_ is a cpdef method. Unfortunately, Python/Cython? tends to confuse cpdef/cdef methods when one creates a class inheriting from two different cdef classes. Here, it means that Homset._get_action_ is not available when one defines sage.modular.abvar.homspace.EndomorphismSubring as subclass of both Homset and Ring.

Solution of this problem: Drop Ring. Instead, implement the ring properties of EndomorphismSubring by using the category framework.

These timings show the advantage of using actions (in each example, the first timing is with both patches, the second timing is with the first patch only):

  1. Both patches
            sage: A = ModularForms(1, 4)
            sage: B = ModularForms(1, 16)
            sage: C = ModularForms(1, 28)
            sage: F = A.Hom(B)(matrix(QQ,1,2,srange(1, 3)))
            sage: G = B.Hom(C)(matrix(QQ,2,3,srange(1, 7)))
            sage: %timeit x=G*F
            10000 loops, best of 3: 95.8 us per loop
    
    Only first patch:
            sage: %timeit x=G*F
            10000 loops, best of 3: 117 us per loop
    
  1. Both patches
            sage: from sage.categories.morphism import SetMorphism
            sage: X.<x> = ZZ[]
            sage: Y = ZZ
            sage: Z = QQ
            sage: phi_xy = SetMorphism(Hom(X, Y, Rings()), lambda p: p[0])
            sage: phi_yz = SetMorphism(Hom(Y, Z, CommutativeAdditiveMonoids()), lambda y: QQ(y)/2)
            sage: %timeit x = phi_yz * phi_xy
            100000 loops, best of 3: 6.37 us per loop
    
    Only first patch:
            sage: %timeit x = phi_yz * phi_xy
            100000 loops, best of 3: 14.8 us per loop
    
  1. Both patches:
            sage: R.<x,y> = QQ[]
            sage: S.<a,b> = QQ[]
            sage: f = R.hom([x+y,x-y],R)
            sage: f = R.hom([a+b,a-b])
            sage: g = S.hom([x+y,x-y])
            sage: %timeit x = f*g
            1000 loops, best of 3: 274 us per loop
    
    First patch only:
            sage: %timeit x = f*g
            1000 loops, best of 3: 389 us per loop
    

TODO

Provide another patch, namely for documentation.

Last edited 7 years ago by SimonKing (previous) (diff)

comment:3 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 6 years ago by rws

  • Status changed from needs_review to needs_work
  • Work issues set to documentation

comment:6 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 5 years ago by vbraun_spam

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