Opened 5 months ago

Last modified 7 weeks ago

#31803 new enhancement

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

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-9.5
Component: geometry Keywords:
Cc: gh-kliem, jipilab, tscrim, jhpalmieri, yzh 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 mkoeppe)

... 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 (22)

comment:1 Changed 5 months ago by mkoeppe

  • Branch set to u/mkoeppe/make_combinatorialpolyhedron_an_element_class

comment:2 Changed 5 months ago by git

  • Commit set to 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 5 months ago by git

  • Commit changed from 60f3ddb2d7e9570efb50c71074c326aa9eea6c5c to 4380cd09bdda4b28b797b83d82d3e45eb751d49b

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 5 months ago by git

  • Commit changed from 4380cd09bdda4b28b797b83d82d3e45eb751d49b to 80026c213daedc6c28715df6a673f84701d110e0

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 5 months ago by git

  • Commit changed from 80026c213daedc6c28715df6a673f84701d110e0 to f8307daa00f8386eba6eb2c16ee27125ab52592a

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

f8307daCombinatorialPolyhedra: Use the category CombinatorialPolyhedralSets()

comment:6 Changed 5 months ago by mkoeppe

  • Authors set to Matthias Koeppe

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

comment:7 Changed 5 months ago by mkoeppe

  • Cc tscrim added

comment:8 Changed 5 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 5 months ago by mkoeppe

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 5 months ago by git

  • Commit changed from f8307daa00f8386eba6eb2c16ee27125ab52592a to c0c7631695706c8a8c8a85f64313360b051223c5

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

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

comment:11 Changed 4 months ago by mkoeppe

  • Summary changed from Make CombinatorialPolyhedron an element class to Make CombinatorialPolyhedron an element class, define morphisms of combinatorial polyhedral sets

comment:12 Changed 4 months ago by mkoeppe

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

comment:13 Changed 4 months ago by mkoeppe

  • Dependencies set to #30469

comment:14 Changed 4 months ago by mkoeppe

  • Dependencies changed from #30469 to #30469, #31821

comment:15 Changed 4 months ago by git

  • Commit changed from c0c7631695706c8a8c8a85f64313360b051223c5 to 25f7e34b64e7f17d9f2f0b77978f0e0006fd3e4d

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 4 months ago by git

  • Commit changed from 25f7e34b64e7f17d9f2f0b77978f0e0006fd3e4d to 24e2d5d92dc56b770739d5cd93376b0fcfc18218

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

24e2d5dCombinatorialPolyhedraMorphism: Add example

comment:17 Changed 4 months ago by mkoeppe

  • Cc jhpalmieri yzh added

Should SimplicialComplexes become a subcategory of CombinatorialPolyhedralSets?

comment:18 Changed 4 months ago by git

  • Commit changed from 24e2d5d92dc56b770739d5cd93376b0fcfc18218 to df05a1a06f2efdf57760f6eb27ca880ac27fbe1b

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

df05a1aSimplicialComplexes: Make it a subcategory of CombinatorialPolyhedralSets

comment:19 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:20 Changed 2 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:21 Changed 7 weeks ago by git

  • Commit changed from df05a1a06f2efdf57760f6eb27ca880ac27fbe1b to 0a15b4693842ef7d10595401a6bee180947fbd1a

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 7 weeks ago by mkoeppe

  • Dependencies #30469, #31821 deleted
Note: See TracTickets for help on using tickets.