Morphisms and Objects of Categories

[simon-king-jena]

Purpose

Introduce a framework for testing whether or not something is a morphism in a category. See the discussion on sage-algebra. Here is a summary of the discussion.

Methods for categories

Categories C should have a method C.has_morphism(f) answering whether f is a morphism in C. By symmetry, we want a method C.has_object(X), answering whether X is an object in C.

Note that we want X in C to be true if and only if X is an object of C (so, it is synonymous to C.has_object(X)). This currently is not always the case:

sage: P.<x,y> = QQ[]
sage: f = P.hom(reversed(P.gens()))
sage: f in Rings().hom_category()
True

but of course f is not an object of the hom-category (it is only contained in an object of the hom-category).

Class/Set of objects and morphisms

It would be nice to have container classes for the objects and for the morphisms of a category. Then, f in C.morphisms() would be a very natural notation for C.has_morphism(f), and X in C.objects() would be another way of saying X in C.

Of course, since f in C.morphisms() and f in C.objects() are nice notations, they should be as fast as possible -- otherwise, people wouldn't use them.

Further discussion should be put in comments to this ticket.

Depends on #9138
Depends on #11115
Depends on #11780

CC: @nilesjohnson @jpflori

Component: categories

Keywords: objects morphisms containment sd34

Work Issues: Cope with non-unique number fields

Author: Simon King

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

[simon-king-jena]

comment:1

If a category has not its own implementation of a hom-category, currently the join of the hom-categories of its super-categories is chosen. Hence, we have

sage: CommutativeRings().hom_category()
Category of hom sets in Category of rings
sage: WeylGroups().hom_category()
Category of hom sets in Category of sets

I don't like that. One problem is that, for test suites, one would like to have a sample object -- but there is no way to create a sample object for a join of arbitrary categories.

Moreover, the "hom sets in the Category of rings" are simply wrong for the category of commutative rings.

Instead, I suggest to walk through the list of all super categories of self, take the first that has the attribute HomCategory (i.e., has a custom implementation of a hom category), and insert self as argument for that HomCategory:

sage: HopfAlgebrasWithBasis(QQ).hom_category()
Category of hom sets in Category of hopf algebras with basis over Rational Field
sage: WeylGroups().hom_category()
Category of hom sets in Category of weyl groups
sage: type(HopfAlgebrasWithBasis(QQ).hom_category())
<class 'sage.categories.modules_with_basis.ModulesWithBasis.HomCategory'>
sage: type(WeylGroups().hom_category())
<class 'sage.categories.sets_cat.Sets.HomCategory'>

Of course, it may happen that several super categories have different custom implementation of hom categories, and we pick just one. But I think this should be taken care of manually, as join categories have a serious drawback, IMHO.

[nthiery]

comment:2

Hi Simon!

Replying to @simon-king-jena:

If a category has not its own implementation of a hom-category, currently the join of the hom-categories of its super-categories is chosen. Hence, we have

sage: CommutativeRings().hom_category()
Category of hom sets in Category of rings
sage: WeylGroups().hom_category()
Category of hom sets in Category of sets

I don't like that.
...

Yeah. As mentioned in the code and in the road map [1], HomCategory is
just plain broken and needs a full refactoring. I just used the
occasion to create a ticket with design suggestions: #10668.

If you want to improve things in this direction, please jump right
away on #10668; it might actually not be that much work, and every
intermediate step would be just a work around and a waste of time.

Thanks again for your continuous motion toward improving Sage in this
area!

Cheers,
Nicolas

[1] http://trac.sagemath.org/sage_trac/wiki/CategoriesRoadMap

[nilesjohnson]

comment:3

cc me! Thanks :)

[simon-king-jena]

comment:4

Depends on #10496, #10659, #8611, #10467

I wont to get the patch finally off my plate. So, here it is, although it isn't finished yet.

My patch provides the following:

sage: C = Rings()
sage: P.<x,y> = QQ[]
sage: f = P.hom(reversed(P.gens()))
sage: C.has_morphism(f)
True
sage: C.morphisms()
Class of morphisms in category of rings
sage: f in C.morphisms()
True
# Currently, a category is acknowledged as "small"
# iff it is a sub-category of FiniteEnumeratedSets()
sage: FiniteFields().morphisms()
Set of morphisms in category of finite fields
sage: f in FiniteFields().morphisms()
False
sage: P in C
True
sage: C.objects()
Class of objects in category of rings
sage: P in C.objects()
True
sage: FiniteFields().objects()
Set of objects in category of finite fields

Note that I interprete Objects() (the top-category in Sage) as the "category of all classes", although this definition probably is not water-proof:

sage: C.objects().category()
Category of objects
sage: FiniteFields().objects().category()
Category of sets

Some categories have a custom containment test, e.g., the category of fields. The containment test of C.objects() automatically tests whether C has a custom containment, and uses it if it is the case:

sage: PolynomialRing(QQ,[]).category()
Category of commutative rings
sage: PolynomialRing(QQ,[]) in Fields()
True
sage: PolynomialRing(QQ,[]) in Fields().objects()
True

The documentation for the new containers for objects and morphisms are added to the Sage reference manual -- please have a look.

SageObject versus CategoryObject

SageObject and CategoryObject were almost identical. In particular, SageObject provided a method category(), that by default returned the "category of objects". In addition, the specifition says that X is an object of X.category(), i.e., X in X.category().

But that approach yields to quite unnatural constructions. For example, 1.category() used to be the "category of elements of Integer Ring", whatever that means. Worse, one used to have

# Unpatched behaviour: Bug
sage: ZZ.hom([1]) in Rings().hom_category()
True

In other words, a ring homomorphism is considered a homset of the category of rings - of course, it should just be an element of a homset:

# With the patch:
sage: ZZ.hom([1]) in Rings().hom_category()
False
sage: ZZ.hom([1]) in ZZ.Hom(ZZ)
True
sage: ZZ.hom([1]) in Rings().morphisms()
True

Fixing that bug required to re-structure SageObject and CategoryObject:

• I removed category() and _test_category() from SageObject and moved it to CategoryObject (which directly inherits from SageObject anyway).
• I made Element and Map inherit from SageObject, not from CategoryObject, and removed the custom category() for Element. Of course, Parent still inherits from CategoryObject.

Note that by this change, it is now impossible to define nonsense such as Hom(2,3) (2 and 3 used to be objects in a category, so, there was a hom-set!).

Hom-categories

Compare #10668: This part of my patch is not finished, yet. I suppose that eventually this ticket here will depend on #10668.

Just for now, I implemented what I described in my previous post. Otherwise, many tests from the new test suites described below would fail.

Test Suites

The test suites of categories have been extended to test against the specification of the new features. In particular, the containers for morphisms and objects provide a test suite. The test suites for C.morphisms() and C.objects() and C.hom_category() are added to the test suite of C.

The patch adds a method an_object() to categories, that is used for additional tests. The default is to return example(), but this is not provided in all cases. The purpose of an_object() is narrower than that of example(), which is supposed to provide a concise instructive (but not necessarily very efficient) implementation. In contrast, an_object() may return an object of a subcategory, if nothing else is available. The test suite of C.an_object() becomes part of the test suite of C.

Similarly, I introduce a method a_morphism. By default, it takes the output of an_object(), tries to create an automorphism by reverting the list of generators, and if that fails then it returns the identity automorphism. The latter sounds trivial, but actually I found several cases where the identity automorphism was provided with the wrong category. This led to the following bug fixes:

• In sage.categories.homset.Hom, there was an assymmetry between the categories of the domain and the codomain. I suggest to choose the meet of both categories. However, note that there was a comment like this:

   To avoid creating superfluous categories, homsets are in the
   homset category of the lowest category which currently says
   something specific about its homsets.

which meant that the endomorphisms of the rational field used to belong to the "Category of hom sets in Category of rings". I didn't observe any problems changing it into the "Category of hom sets in Category of quotient fields".

• Without the patch:

  sage: F = GF(5); MS = MatrixSpace(F,2,2)
  sage: G = MatrixGroup([MS([1,1,0,1])])
  sage: H = MatrixGroup([MS([1,0,1,1])])
  sage: phi = G.hom(H.gens())
  sage: phi.category_for()
  Category of groups
  sage: H.category()
  Category of finite groups
  sage: G.category()
  Category of finite groups
  

  Hence, the morphism belongs to a category that is too broad. With the patch:

  sage: F = GF(5); MS = MatrixSpace(F,2,2)
  sage: G = MatrixGroup([MS([1,1,0,1])])
  sage: H = MatrixGroup([MS([1,0,1,1])])
  sage: phi = G.hom(H.gens())
  sage: phi.category_for()
  Category of finite groups
  

  In several cases I have not been able to find any proper use case in Sage for a given category. In these cases, I have not been able to provide an_object(), so that in these cases I have to skip some tests from the test suites:

• JoinCategory (I guess it is impossible to construct a generic object of the join of two arbitrary categories)

• AbstractCategory (Do I understand correctly that the abstract category for the category of ZZ-modules would be the catogory of modules? I.e., one abstracts the base ring away?)

• Schemes:

  # Bug, not fixed in the patch
  sage: Spec(QQ).category()
  Category of sets
  

• UniqueFactorizationDomains

  # Bug, not fixed in the patch
  sage: ZZ in UniqueFactorizationDomains()
  False
  

• AlgebraModules:

  sage: QQ['x'] in Algebras(QQ)
  True
  # Bug?
  sage: QQ['x']^3 in AlgebraModules(QQ['x'])
  False
  

• GSets (Is there any G-set in Sage that knows that it is a G-set?)

• DualObjectsCategory

• Sets().Subquotients()

• FiniteDimensional...: Most categories whose name starts with FiniteDimensional are not in use.

• PartiallyOrderedMonoids

• MonoidAlgebras

• TensorProductsCategory

• I added a minimal implementation of pointed sets:

  sage: from sage.categories.examples.pointed_sets import PointedSet
  sage: S = PointedSet([1,2,3],2)
  sage: S
  {1, 2, 3} -> 2
  sage: S is loads(dumps(S))
  True
  sage: S == PointedSet([1,2,3],3)
  False
  

• I fixed the category of partially ordered sets.

  Without patch:

  sage: from sage.combinat.posets.posets import Poset
  sage: elms = [1,2,3,4,5,6,7]
  sage: rels = [[1,2],[3,4],[4,5],[2,5]]
  sage: Poset((elms, rels), cover_relations = True).category()
  Category of sets
  

  With the patch, we obtain Category of partially ordered sets.

• The category of matrix algebras has not been used. I added the obvious example:

  sage: MatrixSpace(QQ,2).category()
  Category of matrix algebras over Rational Field
  

  which used to be the category of algebras (not: matrix algebras).

Groupoids

Groupoids are considered as a category with a single object. However, this object did not exist. The patch provides it, modeled as an empty set:

sage: G = SymmetricGroup(5)
sage: C = Groupoid(G)
sage: O = C.an_object(); O
Unique object of Groupoid with underlying set SymmetricGroup(5)
sage: len(O)
0
sage: O.an_element()
Traceback (most recent call last):
...
EmptySetError: 

The elements of G correspond to morphisms of its groupoid. I suggest to actually consider them as morphisms (which is stronger than saying they correspond to morphisms):

sage: G.an_element() in C.morphisms()
True

Note that this point of view is needed in order to have a functorial approach towards actions, namely: If we want to view a group action of G on a set S as a functor from the groupoid of G to the category containing S as an object, then

1. we need that functors can map morphisms (see Adding support for morphisms to the category framework #8807), and

2. we need that group elements are considered as morphisms.

Actually, that was the starting point for my work on this ticket.

On the other hand, I do think that considering G as a homset of Groupoid(G) is not a very clean solution. But I believe this could be addressed on a different ticket, as this one is already too long.

Need for Speed

Of course, testing containment in a category C or in C.objects() or in C.morphisms() should be as fast as possible. I did the following:

• I added a shortpath to C.__contains__ and C.objects().__contains__ for the common case that the category of the argument is C.

• C.objects() and C.morphisms() are cached methods. By speed up cached_function and cached_method #8611, the overhead is now pretty small anyway.

• Containment of an object O in a category C relies on testing whether O.category() is a sub-category of C. This is cached, by speed up cached_function and cached_method #8611. In addition, I remove the overhead entirely, by directly accessing the cache.

• The containers for objects and morphisms are implemented in Cython. The default containment test is copied from the category, in order to reduce the overhead of calling a Python function. Therefore, F in O (where O = C.objects()) is sometimes even a little quicker than F in C:

sage: F = GF(5)
sage: C = Rings()
sage: O = C.objects()
sage: F in O
True
sage: timeit('F in O',number=100000)
100000 loops, best of 3: 5.2 µs per loop
sage: timeit('F in C',number=100000)
100000 loops, best of 3: 5.38 µs per loop

Here are some timings. Their purpose is to show that X in C did not slow down (in fact, there is a speed-up in one special case), and that X in C.objects() has almost no overhead compared to X in C.

Setting:

sage: G = SymmetricGroup(5)
sage: P.<x,y> = QQ[]
sage: F = PolynomialRing(QQ,[])
sage: C1 = Rings()
sage: C2 = G.category()
sage: C3 = Fields()

Sanity tests:

# test that X in C.objects() is the same as X in C
# For C1:
sage: P in C1
True
sage: P in C1.objects()
True
sage: G in C1
False
sage: G in C1.objects()
False
sage: F in C1
True
sage: F in C1.objects()
True

# For C2, which is a join (that's a special case):
sage: P in C2
False
sage: P in C2.objects()
False
sage: G in C2
True
sage: G in C2.objects()
True
sage: F in C2
False
sage: F in C2.objects()
False

# For C3 (having a custom containment test):
sage: P in C3
False
sage: P in C3.objects()
False
sage: G in C3
False
sage: G in C3.objects()
False
sage: F in C3
True
sage: F in C3.objects()
True

Timings without the new patch (but with #10496, #10659, #8611 and #10467):

# containment in C1
sage: timeit('P in C1',number=100000)
100000 loops, best of 3: 11.1 µs per loop
sage: timeit('G in C1',number=100000)
100000 loops, best of 3: 4.32 µs per loop
sage: timeit('F in C1',number=100000)
100000 loops, best of 3: 11.9 µs per loop
# containment in C2
sage: timeit('P in C2',number=100000)
100000 loops, best of 3: 11.1 µs per loop
sage: timeit('G in C2',number=100000)
100000 loops, best of 3: 4.2 µs per loop
sage: timeit('F in C2',number=100000)
100000 loops, best of 3: 11.5 µs per loop
# containment in C3 (custom test for fields!)
sage: timeit('P in C3',number=100000)
100000 loops, best of 3: 16.1 µs per loop
sage: timeit('G in C3',number=100000)
100000 loops, best of 3: 20.5 µs per loop
sage: timeit('F in C3',number=100000)
100000 loops, best of 3: 17.9 µs per loop

Timings with the patch, including the new syntax X in C.objects():

# containment in C1
sage: timeit('P in C1',number=100000)
100000 loops, best of 3: 9.29 µs per loop
sage: timeit('P in C1.objects()',number=100000)
100000 loops, best of 3: 9.85 µs per loop
sage: timeit('G in C1',number=100000)
100000 loops, best of 3: 1.91 µs per loop
sage: timeit('G in C1.objects()',number=100000)
100000 loops, best of 3: 2.45 µs per loop
sage: timeit('F in C1',number=100000)
100000 loops, best of 3: 9.51 µs per loop
sage: timeit('F in C1.objects()',number=100000)
100000 loops, best of 3: 10.2 µs per loop
# containment in C2
sage: timeit('P in C2',number=100000)
100000 loops, best of 3: 9.2 µs per loop
sage: timeit('P in C2.objects()',number=100000)
100000 loops, best of 3: 9.85 µs per loop
# using the shortpath, as G.category() is C2
sage: timeit('G in C2',number=100000)
100000 loops, best of 3: 836 ns per loop
sage: timeit('G in C2.objects()',number=100000)
100000 loops, best of 3: 1.52 µs per loop
sage: timeit('F in C2',number=100000)
100000 loops, best of 3: 9.52 µs per loop
sage: timeit('F in C2.objects()',number=100000)
100000 loops, best of 3: 10.3 µs per loop
# containment in C3 (custom test for fields!)
sage: timeit('P in C3',number=100000)
100000 loops, best of 3: 14 µs per loop
sage: timeit('P in C3.objects()',number=100000)
100000 loops, best of 3: 15.9 µs per loop
sage: timeit('G in C3',number=100000)
100000 loops, best of 3: 15.7 µs per loop
sage: timeit('G in C3.objects()',number=100000)
100000 loops, best of 3: 18.3 µs per loop
sage: timeit('F in C3',number=100000)
100000 loops, best of 3: 15.6 µs per loop
sage: timeit('F in C3.objects()',number=100000)
100000 loops, best of 3: 17.3 µs per loop

Or, directly testing containment in the class of objects:

sage: O1 = C1.objects()
sage: O2 = C2.objects()
sage: O3 = C3.objects()
sage: timeit('P in O1',number=100000)
100000 loops, best of 3: 8.88 µs per loop
sage: timeit('G in O1',number=100000)
100000 loops, best of 3: 1.56 µs per loop
sage: timeit('F in O1',number=100000)
100000 loops, best of 3: 9.31 µs per loop
sage: timeit('P in O2',number=100000)
100000 loops, best of 3: 8.94 µs per loop
sage: timeit('G in O2',number=100000)
100000 loops, best of 3: 704 ns per loop
sage: timeit('F in O2',number=100000)
100000 loops, best of 3: 9.29 µs per loop
sage: timeit('P in O3',number=100000)
100000 loops, best of 3: 14.9 µs per loop
sage: timeit('G in O3',number=100000)
100000 loops, best of 3: 17.1 µs per loop
sage: timeit('F in O3',number=100000)
100000 loops, best of 3: 16.5 µs per loop

[simon-king-jena]

Author: Simon King

[simon-king-jena]

comment:5

So, what's the status of the ticket?

I need more info!

First thing: I am still not happy with the groupoids. But can this perhaps be solved in a different ticket?

Second and more urgent thing? Why does my example of pointed sets not inherit from PointedSets().parent_class? What did I do wrong? I asked on sage-support, but didn't receive a reply.

The problem is:

sage: from sage.categories.examples.pointed_sets import PointedSet
sage: S = PointedSet([1,2,3],2)
sage: S.category()
Category of pointed sets
sage: S.__class__
<class 'sage.categories.examples.pointed_sets.PointedSet_with_category'>

So, the category is initialised. But:

sage: isinstance(S,PointedSets().parent_class)
False

What goes wrong in my implementation?

[nthiery]

comment:6

Hi Simon!

I have only browsed quickly through this yet. I'll try to have a look
soon at the broken parent you mention in the other comment. Just some
small comments before heading for my bed.

• In sage.categories.homset.Hom, there was an assymmetry between the categories of the domain and the codomain. I suggest to choose the meet of both categories. However, note that there was a comment like this:

   To avoid creating superfluous categories, homsets are in the
   homset category of the lowest category which currently says
   something specific about its homsets.

which meant that the endomorphisms of the rational field used to belong to the "Category of hom sets in Category of rings". I didn't observe any problems changing it into the "Category of hom sets in Category of quotient fields".

I wrote this comment. This won't break indeed, but there might
eventually be a penalty in creating that many categories. I need to
think back about it, but this comment might become irrelevant since we
are going to break the inheritance in-between hom categories.

• AbstractCategory (Do I understand correctly that the abstract category for the category of ZZ-modules would be the catogory of modules? I.e., one abstracts the base ring away?)

As I said, don't bother understanding: that's going to be removed. If
it gets in your way, just kill the beast, and remove right now
everything about AbstractCategory (typically by taking over the
appropriate bits of the patch I mentioned).

[simon-king-jena]

comment:7

Thanks to Nicolas for his comments on sage-algebra explaining why my example of pointed sets didn't work well. It is now fixed. Hence, ready for review!

[simon-king-jena]

comment:8

I updated the patch, so that it now applies to sage-4.6.2.alpha4. There are no dependencies.

[simon-king-jena]

comment:9

Since the patchbot keeps complaining that the patch did not apply to good old sage-4.6.1 and since I just verified once again that the patch cleanly applies to sage-4.6.2.alpha4, I replaced the patch by an identical copy and hope that it pushes the patchbot to try it another time with the new sage version.

[simon-king-jena]

comment:10

On #9054, William expressed his anger about category containment tests being too slow. That reminded me of the ticket here. Since the patches do not apply, it needs work. But I guess it is worth while to resume work on that ticket.

[simon-king-jena]

comment:11

I have updated the patch, so that it should apply against sage-4.7.2.alpha2. I did not run tests, yet. Here are some timings:

sage: from sage.rings.commutative_ring import is_CommutativeRing
sage: %timeit is_CommutativeRing(QQ)
625 loops, best of 3: 1.09 µs per loop
sage: C = CommutativeRings().objects()
sage: %timeit QQ in C
625 loops, best of 3: 3.82 µs per loop

is_CommutativeRing simply tests whether QQ is an instance of sage.rings.ring.CommutativeRing, which is of course very fast (but not very reliable from a mathematical point of view.

Anyway, I try to squeeze QQ in C a bit more.

[simon-king-jena]

comment:12

I created a new version of my patch. The aim is to make the performance of containment tests even better. I did the following, compared with the old patch:

• I make the patch dependent on Categories for all rings #9138 and Rewrite cached_method in Cython #11115 (both help to come to speed).

• I've put power series rings into the category and coercion framework.

• I introduced base() for join categories: If at least one of the underlying categories has a base and if there is no conflict with different bases, then the join shall have that base as well. That is needed because some algebras have a join category by Categories for all rings #9138.

• SimplicialComplex has not been derived from CategoryObject, even though its instances are objects of a category! I corrected it.

• GroupAlgebras should not only be Hopf algebras with basis but also group algebras. Hence, I made it a join of the two.

• I implemented is_supercategory (there has only been is_subcategory), and use it to make containment tests even faster. It depends on Rewrite cached_method in Cython #11115, because I use the Cython class of cached methods.

I guess the best news is that the containment test via category framework can now compete with a pure class check, if that class check is done in Python. I take, for example, commutative rings:

sage: from sage.rings.commutative_ring import is_CommutativeRing
sage: is_CommutativeRing??
Type:           function
Base Class:     <type 'function'>
String Form:    <function is_CommutativeRing at 0x118c488>
Namespace:      Interactive
File:           /mnt/local/king/SAGE/sandbox/sage-4.7.2.alpha2/local/lib/python2.6/site-packages/sage/rings/commutative_ring.py
Definition:     is_CommutativeRing(R)
Source:
def is_CommutativeRing(R):
    return isinstance(R, CommutativeRing)
sage: is_CommutativeRing(QQ)
True
sage: s = SymmetricGroup(4)
sage: is_CommutativeRing(s)
False
sage: %timeit is_CommutativeRing(QQ)
625 loops, best of 3: 1.09 µs per loop
sage: %timeit is_CommutativeRing(s)
625 loops, best of 3: 3.51 µs per loop

Since is_CommutativeRing just tests the class, it is supposed to be very fast. But let us compare with the generic containment test in the category of commutative rings and in the class of objects of that category:

sage: C = CommutativeRings()
sage: O = C.objects()
sage: QQ in C
True
sage: QQ in O
True
sage: s in C
False
sage: s in O
False
sage: %timeit QQ in C
625 loops, best of 3: 4.62 µs per loop
# Timing in sage-4.6.2: 12.9 µs per loop
sage: %timeit QQ in O
625 loops, best of 3: 1.5 µs per loop
sage: %timeit s in C
625 loops, best of 3: 4.69 µs per loop
# Timing in sage-4.6.2: 10.2 µs per loop
sage: %timeit s in O
625 loops, best of 3: 1.46 µs per loop

Hence, is_CommutativeRing(s) is slower than s in O, where O = CommutativeRings().objects().

The reason for that speedup is Cython. While is_CommutativeRing is a Python function, the objects of a category are implemented in Cython. Moreover, category containment is tested by the cached method is_supercategory, which also is in Cython by #9138.

Caveat: I did not run the full tests, yet, and I would like to try and remove some custom containment tests in the category framework, that tend to be slower than the generic test and might not be needed with #9138.

[simon-king-jena]

Dependencies: #9138, #11115

[simon-king-jena]

comment:13

I forgot to mention that I also improved is_Ring.

With sage-4.7.2.alpha1 plus #9138 and #11115:

sage: from sage.rings.ring import is_Ring
sage: MS = MatrixSpace(QQ,2)
sage: %timeit is_Ring(QQ)
625 loops, best of 3: 5.1 µs per loop
sage: %timeit is_Ring(MS)
625 loops, best of 3: 17.3 µs per loop
sage: C = Rings()
sage: %timeit QQ in C
625 loops, best of 3: 4.18 µs per loop
sage: %timeit MS in C
625 loops, best of 3: 4.31 µs per loop

With sage-4.7.2.alpha2 plus #9138 and #11115 and the patch from here:

sage: from sage.rings.ring import is_Ring
sage: MS = MatrixSpace(QQ,2)
sage: %timeit is_Ring(QQ)
625 loops, best of 3: 259 ns per loop
sage: %timeit is_Ring(MS)
625 loops, best of 3: 17.5 µs per loop
sage: C = Rings().objects()
sage: %timeit QQ in C
625 loops, best of 3: 1.49 µs per loop
sage: %timeit MS in C
625 loops, best of 3: 1.57 µs per loop

[simon-king-jena]

comment:14

I leave it as "needs review", but I think I have to adopt the Cython improvements on morphism containment tests as well.

[simon-king-jena]

Work Issues: doctests

[simon-king-jena]

comment:15

Replying to @simon-king-jena:

I leave it as "needs review", but I think I have to adopt the Cython improvements on morphism containment tests as well.

Nope, it wouldn't easily work for the morphisms.

It turns out that I have to fix many doctests.

[simon-king-jena]

comment:53

Replying to @nthiery:

I am glad that UniqueRepresentation works well :-)

I am not 100% certain that they work well. At least for getting the tests of elliptic curves pass, we probably need #11670 (uniqueness of number fields). And note that (currently) I only introduce UniqueRepresentation to homsets of rings. I did not try to have it for all parents.

Agreed, the more unique parents, the better. But you don't have to fix
all of Sage misfeatures in just this patch :-)

But all that were uncovered by new tests introduced with this patch.

Besides, I am still not yet sure that we want to strictly enforce 100%
unique parents. There might be occasional exceptions -- I don't know,
things like temporarily created parents or what not -- where we might
want to not have uniqueness.

Why would one not want uniqueness for temporarily created parents? When the same parent is frequently created, then it is more efficient to just use a cache. Or are you concerned that one creates too many different parents that will stay in cache forever?

Ok. I could see other use cases. Should this be a method of
UniqueRepresentation -- of course still for internal use ?

No, what I just wrote can't be a method of UniqueRepresentation. Here is the purpose of what I wrote: Let X be a ring; X._remove_from_homset_cache() removes Hom(X,Y) and Hom(Y,X) from cache, for any ring Y.

Hence, it is not X.__class__.__classcall__.cache that is cleared, but X.category().hom_category().parent_class.__classcall__.cache. And an item is removed from the cache not if X is the value of that item, but if X appears in the key of the item.

But I think it would be a good idea to add a X._reduce_from_cache() method to UniqueRepresentation: It would remove any item of X.__class__.__classcall__.cache whose value is (equal to) X, and then it would try X._reduce_from_homset_cache() as well (which would of course only be available for rings).

[simon-king-jena]

comment:54

It turns out that #11670 will not solve the problem. But it seems to me that I come closer to a solution: In contrast to many other cases, hom sets of number fields are not unique parents. With my patch, they are even less unique. Here is a show case:

sage-4.6.2

sage: N = NumberField(x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, 'a') 
sage: Hom(N,N) is Hom(N,N)
False
sage: Hom(N,N) == Hom(N,N)
True

With my patch, we still have

sage: N = NumberField(x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, 'a') 
sage: Hom(N,N) is Hom(N,N)
False

but then

sage: Hom(N,N) == Hom(N,N)
False

I don't know yet why this is the case, because the __cmp__ function of number field homsets did not change.

[simon-king-jena]

comment:55

Aha! I understand!

Hom(N,N) reduces to N._Hom_(N), which directly constructs a number field hom set.

By consequence, Hom(N,N) does not become a unique parent, even though it inherits from UniqueRepresentation via inheritance from the category. But that inheritance takes place after creation of the hom set, so that it is too late for Rings().HomCategory.ParentMethods.__classcall__.

In other words: Via category inheritance, Hom(N,N) inherits __eq__ from UniqueRepresentation, which is used for comparison and precedes the use of the custom __cmp__ method of number field homsets. However, __eq__ expects unique parents.

We thus have:

age: N = NumberField(x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, 'a')
sage: H = Hom(N,N)
sage: H == Hom(N,N)
False
sage: H > Hom(N,N)
False
sage: H < Hom(N,N)
False

I guess, until number fields are truly unique parents, I should add an __eq__ to number field hom sets, in order to not have it inherited from UniqueRepresentation.

[simon-king-jena]

comment:56

I think I found a valid work-around: Sometimes, a number field is created with passing the option cache=False to the number field constructor. If that option is used, I suggest to call the new _remove_from_homset_cache. It seems to work!

With that change (not yet posted), we have

sage: E = EllipticCurve('389a'); P = E.heegner_point(-7, 5); P
Heegner point of discriminant -7 and conductor 5 on elliptic curve of conductor 389
sage:  z = P.point_exact(100, optimize=True)

With the old patch, one would have the following error:

AssertionError: BUG in coercion model
    Apparently there are two versions of
        Number Field in a with defining polynomial x^12 + 4*x^11 + 56*x^10 + 170*x^9 + 1130*x^8 + 2564*x^7 + 10791*x^6 + 18054*x^5 + 51340*x^4 + 57530*x^3 + 102986*x^2 + 53724*x + 35001
    in the cache.

Running doctests, and then I hope the most serious problems have finally disappeared...

[simon-king-jena]

Changed work issues from Cartesian products to Cope with non-unique number fields

[nthiery]

comment:57

Replying to @simon-king-jena:

Why would one not want uniqueness for temporarily created parents? When the same parent is frequently created, then it is more efficient to just use a cache. Or are you concerned that one creates too many different parents that will stay in cache forever?

Possibly so. Or about creating many different parents that each need a
lot of input data, or maybe some non hashable data; and maybe you need
each such parent only once. So the overhead in time or code complexity
of guaranteeing unique representation would not be worth it.

Honestly, I don't have a specific use case, just a bad feeling about
it.

But I think it would be a good idea to add a X._reduce_from_cache() method to UniqueRepresentation: It would remove any item of X.__class__.__classcall__.cache whose value is (equal to) X,

+1. I am not sure about the name though. What about something like
_delete_from_cache instead?

and then it would try X._reduce_from_homset_cache() as well (which
would of course only be available for rings).

UniqueRepresentation is meant to also be used by non Parents. So I'd
rather have nothing Parent-related in it. On the other hand, Parent
could overload UniqueRepresentation's method to also call that for
homsets.

Cheers,
Nicolas

[nthiery]

comment:58

Hi Simon,

Replying to @simon-king-jena:

Aha! I understand!

:-)

I guess, until number fields are truly unique parents, I should add an __eq__ to number field hom sets, in order to not have it inherited from UniqueRepresentation.

I am not very keen on having a class inherit (indirectly) from
UniqueRepresentation, and then hacking it's way around to actually not
have to implement the unique representation protocole. I'd rather only
inherit explicitly from UniqueRepresentation when I mean it.

Cheers,

[simon-king-jena]

comment:59

Replying to @nthiery:

But I think it would be a good idea to add a X._reduce_from_cache() method to UniqueRepresentation: It would remove any item of X.__class__.__classcall__.cache whose value is (equal to) X,

+1. I am not sure about the name though. What about something like
_delete_from_cache instead?

Sorry, I meant to write _remove_from_cache, not _reduce_from_cache.

and then it would try X._reduce_from_homset_cache() as well (which
would of course only be available for rings).

UniqueRepresentation is meant to also be used by non Parents.

And _reduce_from_homset_cache is only for those parents that happen to belong to the category of rings. That's why I write "try ... (which would ... only be available for rings)". It would not be available for non-rings, and in particular not for non-parents. So, no problem, the attribute error would be caught anyway.

Parent
could overload UniqueRepresentation's method to also call that for
homsets.

No, it could not, because most parents are no UniqueRepresentations.

[simon-king-jena]

comment:60

Replying to @nthiery:

I am not very keen on having a class inherit (indirectly) from
UniqueRepresentation, and then hacking it's way around to actually not
have to implement the unique representation protocole. I'd rather only
inherit explicitly from UniqueRepresentation when I mean it.

Yes, what I did doesn't fully convince me.

With my patch, the Rings().HomCategory.ParentMethods inherits from UniqueRepresentation, and since NumberFields() is a sub-category of Rings(), the default NumberFields().hom_category().parent_class inherits from UniqueRepresentation` as well.

But it would be possible to have a custom NumberFields().HomCategory.ParentMethods, similar to the custom Rings().HomCategory.ParentMethods.

While Rings().hom_category().parent_class with my patch inherits from UniqueRepresentation and (via classcall) from either sage.rings.homset.RingHomset_generic or sage.rings.homset.RingHomset_quo_ring, one could have NumberFields().hom_category().parent_class inherit from sage.rings.number_field.morphism.NumberFieldHomset, but not from UniqueRepresentation.

[simon-king-jena]

comment:61

Next: I accidentally found that quotient rings are no unique parents either.

I guess they should be, right?

[simon-king-jena]

comment:62

Replying to @simon-king-jena:

Next: I accidentally found that quotient rings are no unique parents either.

I guess they should be, right?

Dealt with on a different ticket, I mean...

[nthiery]

comment:63

Replying to @simon-king-jena:

But it would be possible to have a custom NumberFields().HomCategory.ParentMethods, similar to the custom Rings().HomCategory.ParentMethods.

While Rings().hom_category().parent_class with my patch inherits from UniqueRepresentation and (via classcall) from either sage.rings.homset.RingHomset_generic or sage.rings.homset.RingHomset_quo_ring, one could have NumberFields().hom_category().parent_class inherit from sage.rings.number_field.morphism.NumberFieldHomset, but not from UniqueRepresentation.

Sound good.

[nthiery]

comment:64

Replying to @simon-king-jena:

And _reduce_from_homset_cache is only for those parents that
happen to belong to the category of rings. That's why I write "try
... (which would ... only be available for rings)". It would not be
available for non-rings, and in particular not for non-parents. So,
no problem, the attribute error would be caught anyway.

Yes, it would work. Yet, in a perfect world, UniqueRepresentation
ought to be generalized outside of Sage, as a general purpose Python
tool (even though I am not sure anyone will take the time for
that). So having some logic in there specifically targetted toward
homsets smells. But maybe it's just a question of finding a more
general name for this hook.

No, it could not, because most parents are no UniqueRepresentations.

Good point :-)

[simon-king-jena]

comment:65

I am not sure if the attached patch is up to date. Unfortunately, applying it to sage-4.7.2.alpha3 gives 5 hunks that fail to apply. I hope that I'll be able to get finally a working version during the upcoming sage days 34.

[simon-king-jena]

Changed keywords from objects morphisms containment to objects morphisms containment sd34

[simon-king-jena]

comment:70

Let us see if anything from this patch could be useful in the current state of the art. See #10668 and #16340.