Opened 19 months ago

Last modified 3 months ago

#31803 new enhancement

Make CombinatorialPolyhedron an element class, define morphisms of combinatorial polyhedral sets

Reported by: Matthias Köppe Owned by:
Priority: major Milestone: sage-9.8
Component: geometry Keywords:
Cc: gh-kliem, Jean-Philippe Labbé, Travis Scrimshaw, John Palmieri, Yuan Zhou Merged in:
Authors: Matthias Koeppe Reviewers:
Report Upstream: N/A Work issues:
Branch: u/mkoeppe/make_combinatorialpolyhedron_an_element_class (Commits, GitHub, GitLab) Commit: 0a15b4693842ef7d10595401a6bee180947fbd1a
Dependencies: Stopgaps:

Status badges

Description (last modified by Matthias Köppe)

... of a parent class CombinatorialPolyhedra in a new category of CombinatorialPolyhedralSets. A parent is defined by (possibly infinite) sets of allowed vertices and facets; every element's set of vertices and facets is a subset of these.

Morphisms in the category:

  • permutations of the Vrep
  • permutations of the Hrep
  • relabelings of the Vrep
  • relabelings of the Hrep
  • degenerations.

This setup of element/parent/category is parallel to geometric polyhedra: Polyhedron/Polyhedra/PolyhedralSets.

Assigning coordinates in QQ^3 to labeled vertices then defines a morphism from CombinatorialPolyhedra(vertices, facets) to Polyhedra(QQ, 3).

Change History (25)

comment:1 Changed 19 months ago by Matthias Köppe

Branch: u/mkoeppe/make_combinatorialpolyhedron_an_element_class

comment:2 Changed 19 months ago by git

Commit: 60f3ddb2d7e9570efb50c71074c326aa9eea6c5c

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

60f3ddbCombinatorialPolyhedra: New parent class, use it to make CombinatorialPolyhedron an element class

comment:3 Changed 19 months ago by git

Commit: 60f3ddb2d7e9570efb50c71074c326aa9eea6c5c4380cd09bdda4b28b797b83d82d3e45eb751d49b

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

4380cd0src/sage/geometry/polyhedron/combinatorial_polyhedron/parent.py: Add missing imports

comment:4 Changed 19 months ago by git

Commit: 4380cd09bdda4b28b797b83d82d3e45eb751d49b80026c213daedc6c28715df6a673f84701d110e0

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

67d1e89CombinatorialPolyhedralSets: Add element methods dim/dimension, subcategory Finite with parent method dimension
80026c2PolyhedralSets: Make it a subcategory of CombinatorialPolyhedralSets

comment:5 Changed 19 months ago by git

Commit: 80026c213daedc6c28715df6a673f84701d110e0f8307daa00f8386eba6eb2c16ee27125ab52592a

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

f8307daCombinatorialPolyhedra: Use the category CombinatorialPolyhedralSets()

comment:6 Changed 19 months ago by Matthias Köppe

Authors: Matthias Koeppe

Here's a beginning, without adding anything useful yet.

comment:7 Changed 19 months ago by Matthias Köppe

Cc: Travis Scrimshaw added

comment:8 Changed 19 months ago by gh-kliem

Thanks for taking care of this.

I have no experience with categories and what is best practice there. But I think it makes sense to mention my ideas/plans for this module so they can be considered if they need to.

Status quo (from my point of view):

CombinatorialPolyhedron is mainly a wrapper around FaceIterator. To make it complete, there is also PolyhedronFaceLattice which collects all faces from the FaceIterator and calculates all the cover relations.

FaceIterator works for simplicial complexes and for the intersection lattice of reflection groups of a root system (as in ReflectionGroup(['E',6])).

Plans, Ideas:

  • #31245 uses the FaceIterator in parallel for the f-vector. This parallel approach is applicable to other problems.
  • Now that we use data_structures/bitset the underlying bitsets are much easier to handle. This allows doing polyhedral constructions just on the combinatorial polyhedron (and trusting bitsets to do the right thing instead of rethinking everything).
  • Eventually some of the code should be moved to a more generic place in sage. Probably it makes sense to have CombinatorialPolyhedron inherit from a more generic interface to FaceIterator. (I'm currently waiting for #31245). Then simplicial complexes and reflection groups should have access to it as well. In the end it is just an iterator that works over lattices with one of the following properties (atomic = all elements are joins of atoms):
    • intervals of length 2 contain at least 2 elements (true for polytopes and true enough for unbounded polyhedra)
    • simplicial coatomic lattices (or the dual thing) -- a lattice where each interval not containing the upper bound is boolean (true for simplicial complexes and for simplicial polytopes), this iterator is much faster than the previous version
    • it would also for atomic and coatomic lattices in general with some minor changes (however, I don't see a use case yet)
  • There is still the big agenda that CombinatorialPolyhedron should replace all combinatorial things in cones, lattice polytopes and polyhedra. In particular it should deprecate sage/src/sage/geometry/hasse_diagram.py.

comment:9 Changed 19 months ago by Matthias Köppe

Thanks a lot for sharing this valuable perspective.

Regarding PolyhedronFaceLattice, perhaps this could become a parent class in the categories CombinatorialPolyhedralSets and FiniteLatticePosets. (Currently you go through making a digraph and calling Poset -- perhaps this can be implemented more directly.)

I think most of the other things are orthogonal to this ticket.

comment:10 Changed 19 months ago by git

Commit: f8307daa00f8386eba6eb2c16ee27125ab52592ac0c7631695706c8a8c8a85f64313360b051223c5

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

c0c7631sage.geometry.polyhedron.combinatorial_polyhedron.{homset,morphism}: New

comment:11 Changed 19 months ago by Matthias Köppe

Summary: Make CombinatorialPolyhedron an element classMake CombinatorialPolyhedron an element class, define morphisms of combinatorial polyhedral sets

comment:12 Changed 19 months ago by Matthias Köppe

Missing: The actual implementation of the morphism (CombinatorialPolyhedraMorphism.__call__ method).

comment:13 Changed 19 months ago by Matthias Köppe

Dependencies: #30469

comment:14 Changed 19 months ago by Matthias Köppe

Dependencies: #30469#30469, #31821

comment:15 Changed 19 months ago by git

Commit: c0c7631695706c8a8c8a85f64313360b051223c525f7e34b64e7f17d9f2f0b77978f0e0006fd3e4d

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

3896c32fix naming and fix a doctest
82db408reintroduce spaces to fix merge conflict
f460b23improve documentation
479f743better variable names for documentation
ab9d41eMerge #30469
79983a9fix pickling of representation objects with backend normaliz
5e65a5eadd doctest
b285d95run testsuite on combinatorial polyhedron
db82c83Merge #31821
25f7e34CombinatorialPolyhedron: Make it a factory function, rename class to CombinatorialPolyhedron_class

comment:16 Changed 19 months ago by git

Commit: 25f7e34b64e7f17d9f2f0b77978f0e0006fd3e4d24e2d5d92dc56b770739d5cd93376b0fcfc18218

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

24e2d5dCombinatorialPolyhedraMorphism: Add example

comment:17 Changed 18 months ago by Matthias Köppe

Cc: John Palmieri Yuan Zhou added

Should SimplicialComplexes become a subcategory of CombinatorialPolyhedralSets?

comment:18 Changed 18 months ago by git

Commit: 24e2d5d92dc56b770739d5cd93376b0fcfc18218df05a1a06f2efdf57760f6eb27ca880ac27fbe1b

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

df05a1aSimplicialComplexes: Make it a subcategory of CombinatorialPolyhedralSets

comment:19 Changed 18 months ago by Matthias Köppe

Description: modified (diff)

comment:20 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:21 Changed 16 months ago by git

Commit: df05a1a06f2efdf57760f6eb27ca880ac27fbe1b0a15b4693842ef7d10595401a6bee180947fbd1a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f9d15f3sage.categories.polyhedra (PolyhedralSets): Explain what the parents and elements are
1f1922asage.categories.combinatorial_polyhedral_sets: New
6728fdcCombinatorialPolyhedra: New parent class, use it to make CombinatorialPolyhedron an element class
ced1988CombinatorialPolyhedralSets: Add element methods dim/dimension, subcategory Finite with parent method dimension
633db6dPolyhedralSets: Make it a subcategory of CombinatorialPolyhedralSets
c3ccc63CombinatorialPolyhedra: Use the category CombinatorialPolyhedralSets()
05aa347sage.geometry.polyhedron.combinatorial_polyhedron.{homset,morphism}: New
0aa274fCombinatorialPolyhedron: Make it a factory function, rename class to CombinatorialPolyhedron_class
d0243fbCombinatorialPolyhedraMorphism: Add example
0a15b46SimplicialComplexes: Make it a subcategory of CombinatorialPolyhedralSets

comment:22 Changed 16 months ago by Matthias Köppe

Dependencies: #30469, #31821

comment:23 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:24 Changed 8 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:25 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.