Categories for Cones

[mkoeppe]

Right now a Cone is not a parent, and it does not have a specific category.

sage: C = Cone([[1,0], [1,5]])
sage: C.category()
Category of objects

I am wondering whether suitable categories, such as SemiModules (here, using the monoid of nonnegative integers), Cones (nonnegative reals), ... should be set up. This category framework should then be general enough to represent other (non-polyhedral) cones, such as the cone of convex functions of a real variable; the cone of semidefinite matrices; etc.

Also, there should be a method to create the affine semigroup of the integer points in a cone (its generators are computed by the method semigroup_generators) as a monoid.

CC: @tscrim @novoselt @nthiery

Component: categories

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

[tscrim]

comment:1

You can do more than 1 category, i.e. create a subcategory for polyhedral cones. However, right now we unfortunately have (very) limited support for categories with just objects (those that don't fit into the Parent-Element setup) (unless I am forgetting something, Nicolas?). So you might run into this technical limitation if you wanted to pull generic object code into the category, unless you are thinking of making cones a parent with an element class? Nevertheless, there could likely be code for morphisms and functors you could be able to apply.

[mkoeppe]

comment:2

Replying to @tscrim:

[...] unless you are thinking of making cones a parent with an element class?

That's part of what I am trying to figure out. Likewise, for polyhedra and the points contained in them - there is also no parent/element relationship at the moment.

[novoselt]

comment:3

But points of a cone/polyhedron are elements of a vector space parent. Do you want to wrap them up for the sake of points knowing that they belong to a certain cone? With different instances for the same point belonging to different cones? The setup for toric cones etc. was that generating points are shared between related structures, as in they are the same objects to decrease memory consumption and increase speed of construction.

[mkoeppe]

comment:4

Replying to @novoselt:

But points of a cone/polyhedron are elements of a vector space parent. Do you want to wrap them up for the sake of points knowing that they belong to a certain cone? With different instances for the same point belonging to different cones? The setup for toric cones etc. was that generating points are shared between related structures, as in they are the same objects to decrease memory consumption and increase speed of construction.

Thanks for sharing this perspective and background. However it seems that it is a goal in Sage that "every set should be a parent". Perhaps Facade sets can help to reconcile this goal and the goal of efficiency?

[novoselt]

comment:5

Replying to @mkoeppe:

Thanks for sharing this perspective and background. However it seems that it is a goal in Sage that "every set should be a parent".

Can you please clarify "seems"? Do we have some written policy/recommendation for this? Does it cover subsets of bigger sets? I.e. if I have a bunch of subsets of some set S, should elements of each of these subsets have different parents rather than S? Seems quite odd to me. What about parents for operations? Should adding two points belonging to two cones result in constructing the Minkowski sum cone where the result is guaranteed to live???

[mkoeppe]

comment:6

Replying to @novoselt:

Replying to @mkoeppe:

Thanks for sharing this perspective and background. However it seems that it is a goal in Sage that "every set should be a parent".

Can you please clarify "seems"? Do we have some written policy/recommendation for this?

I'm afraid the project is a bit short on policies. It's what I gathered from reading http://doc.sagemath.org/html/en/reference/categories/sage/categories/primer.html, https://trac.sagemath.org/wiki/CategoriesRoadMap etc. and looking at various examples such as posets.

Hoping that people familiar with the category framework can help to clarify.

Does it cover subsets of bigger sets? I.e. if I have a bunch of subsets of some set S, should elements of each of these subsets have different parents rather than S? Seems quite odd to me.

It's already the case as soon as the subsets have enough (algebraic) structure. Example, for point lattices:

sage: L1 = (QQ^2).span([[1, 6], [1,0]], ZZ)
sage: L2 = (QQ^2).span([[1, 3], [1,0]], ZZ)
sage: L1.0
(1, 0)
sage: L2.0
(1, 0)
sage: L1.0 == L2.0
True
sage: L1.0.parent()

Free module of degree 2 and rank 2 over Integer Ring
Echelon basis matrix:
[1 0]
[0 6]
sage: L2.0.parent()

Free module of degree 2 and rank 2 over Integer Ring
Echelon basis matrix:
[1 0]
[0 3]

I guess in the end the question is: Do cones have enough structure to warrant similar behavior? The category- and axiom-based inheritance of methods, including test* methods, seems quite attractive to me, and it would be nice if cones could benefit from this infrastructure.

What about parents for operations? Should adding two points belonging to two cones result in constructing the Minkowski sum cone where the result is guaranteed to live???

It sounds a bit excessive, but that matches the sound of the word "pushout".

[tscrim]

comment:7

If you want to consider a cone is considered as a set of objects (i.e., an object in a concrete category), then it should be a Parent and the elements should be a subclass of Element. If you want to consider them in some objects in a non-concrete category, then I think they should just be a CategoryObject (where we would need to add support for ObjectMethods, but you can work around this for now with an ABC). Be warned, we have yet to really include non-concrete categories, so you are wondering into the wilderness here.

A facade parent P is for when the elements of P would more naturally belong to another parent, but you want to construct them through P.

However, it seems the idea is to consider cones as a vector space but over a semiring (more explicitly, an additive monoid with a distributive multiplicative structure). Perhaps a more simple question, is every module over a (commutative?) ring/field a cone?

The pushout construction of Sage should work well if you do want to have compatible arithmetic and coercion.

[novoselt]

comment:8

I am all for extra features and functionality, especially implemented by others, as long as it does not severely harm "usual" usage. Constructing Minkowski sum of cones when adding a couple of vectors does not sound reasonable to me as it is a very expensive operation for non-trivial cones.

[mkoeppe]

comment:9

Replying to @tscrim:

However, it seems the idea is to consider cones as a vector space but over a semiring (more explicitly, an additive monoid with a distributive multiplicative structure). Perhaps a more simple question, is every module over a (commutative?) ring/field a cone?

One would take the nonnegative elements of an ordered field, not an arbitrary commutative ring. They form a semiring. The (semi)modules over this semiring would be a cone.

A non-example, the nonnegative integer vectors of RR^2 would not form a cone because they are merely a semimodule over Z_+ , not an ordered field (equivalently, an additive monoid).

[mkoeppe]

comment:12

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.