Opened 15 months ago
Last modified 4 months ago
#31799 new enhancement
From CombinatorialPolyhedron and H-representation to Polyhedron (with double description)
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.7 |
Component: | geometry | Keywords: | |
Cc: | gh-kliem, yzh, jipilab | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | u/mkoeppe/from_combinatorialpolyhedron_and_h_representation_to_polyhedron__with_double_description_ (Commits, GitHub, GitLab) | Commit: | 789eadafc5807c003ccf7f8b0611b68760da2d3a |
Dependencies: | #31823, #26366 | Stopgaps: |
Description (last modified by )
Given an (abstract) CombinatorialPolyhedron
such that at least one of H-representation and V-representation are labeled geometrically, the new method CombinatorialPolyhedron.as_polyhedron
constructs a geometric polyhedron.
If check=True
(default), it checks that the result is OK.
We should be able to efficiently build a polyhedron, avoiding to run the double description method when setting up the polyhedron, for the backends that accept double description input:
- if both representations are geometric, just pass them to the polyhedron constructor (#26366)
- if only one representation is geometric, reconstruct the other one from the incidences by equation solving.
Ideally, an optional argument allow_degeneration
would allow that the given representation data actually gives a degeneration of the given combinatorial polyhedron.
In the context of #31803, this would be a morphism.
Change History (20)
comment:1 Changed 15 months ago by
- Description modified (diff)
comment:2 Changed 15 months ago by
- Description modified (diff)
comment:3 follow-ups: ↓ 4 ↓ 5 Changed 15 months ago by
comment:4 in reply to: ↑ 3 Changed 15 months ago by
Replying to gh-kliem:
It only seems to make sense for those backends that allow initialization from both V-representation and H-representation.
Yes, that's right. For the moment I am fine with just creating polyhedra in the field
backend. In fact, my main application will be for parametric polyhedra (where the coefficient field is a ParametricRealField).
(Normaliz somehow allows precomputed data, but it appears that initializing from precomputed data isn't really an advantage in terms of computation time.)
Hopefully at some point this can be improved - but it's not the main direction of this ticket.
The method
a_maximal_chain
can be generalized to allow this. Currently it only gives some maximal chain, but we can easily obtain a maximal chain for each facet. This allows computing a unique inequality for each facet (in the non-degenerate case), given the V-representation.a_maximal_chain
also allows obtaining the equations.Given the H-representation we might as well be lazy and just use
CombinatorialPolyhedron.polar
for this.
Sounds great!
comment:5 in reply to: ↑ 3 ; follow-up: ↓ 7 Changed 15 months ago by
Replying to gh-kliem:
I'm not exactly sure what you mean by
allow_degeneration
. This is what I think for the case that the V-representation is given: [...]
- the slack matrix (of the given V-representation and the computed H-representation) must always be non-negative
Yes
- if
allow_degeneration=False
the incidence matrix (of the given V-representation and the computed H-representation) must be the same as the incidence matrix of the combinatorial polyhedron
Yes, and for allow_degeneration=True
, we would just drop this requirement, I think.
It all depends on how much degeneration we allow.
Let's consider the generalized permutahedron as a model. I would like to include its degenerations in full generality.
A related question is how to do recognize degenerations on the level of abstract combinatorial polyhedra (without coordinates). Given two (abstract) combinatorial polyhedra P, Q and a map sending vertices to vertices, can we detect whether Q is a degeneration of P? I don't know how to check this without coordinates.
comment:6 Changed 15 months ago by
In light of #31801 we should probably add an optional argument verify
with default True
.
comment:7 in reply to: ↑ 5 Changed 15 months ago by
Replying to mkoeppe:
[...]
A related question is how to do recognize degenerations on the level of abstract combinatorial polyhedra (without coordinates). Given two (abstract) combinatorial polyhedra P, Q and a map sending vertices to vertices, can we detect whether Q is a degeneration of P? I don't know how to check this without coordinates.
Ah, ok. From my intuition (which might be wrong as well), the following happens at a degeneration map:
- There exists a list of disjoint faces, which get contracted (so only one vertex remains for each of those faces).
- First step is to contract the vertices according to the map and apply a bitwise OR to the (old) coatom incidences.
- The new coatoms are the inclusion maximal coatoms.
- Each old coatom should still define a face (I think this holds automatically).
What needs to be checked:
- Whether each equivalence class of vertices corresponds to a face (compute the join of those atoms).
If this is correct, this ticket should depend on #29683.
We also need to check that the incidence matrix is correct then, which is quite obvious of course (probably best to check this via the bipartite digraph isomorphism of the vertex-facet graph).
Do we allow degenerations that might be obtained by iteratively degenerating? Might be a bit harder to check.
comment:8 Changed 15 months ago by
- Dependencies set to #31823
comment:9 Changed 15 months ago by
As for designing the interface, I would like to introduce a method CombinatorialPolyhedra.hom
to construct the morphism
(as you suggest, with a verify
(or check
?) keyword argument)
comment:10 Changed 15 months ago by
Should be a check
keyword according to git grep
. verify
is used (almost) exclusively for sage_input
.
comment:11 Changed 15 months ago by
So something like this:
class CombinatorialPolyhedra(UniqueRepresentation, Parent): ... def hom(self, Vrep_dict, codomain=None, check=True, category=None):
comment:12 Changed 15 months ago by
... it should return an instance of a class similar to SimplicialComplexMorphism
comment:13 Changed 15 months ago by
A skeleton of the classes to implement morphisms is now on #31803.
comment:14 Changed 15 months ago by
- Description modified (diff)
comment:15 Changed 15 months ago by
- Dependencies changed from #31823 to #31823, #26366
comment:16 Changed 15 months ago by
- Branch set to u/mkoeppe/from_combinatorialpolyhedron_and_h_representation_to_polyhedron__with_double_description_
comment:17 Changed 15 months ago by
- Commit set to 789eadafc5807c003ccf7f8b0611b68760da2d3a
- Description modified (diff)
comment:18 Changed 13 months ago by
- Milestone changed from sage-9.4 to sage-9.5
comment:19 Changed 8 months ago by
- Milestone changed from sage-9.5 to sage-9.6
comment:20 Changed 4 months ago by
- Milestone changed from sage-9.6 to sage-9.7
It only seems to make sense for those backends that allow initialization from both V-representation and H-representation.
(Normaliz somehow allows precomputed data, but it appears that initializing from precomputed data isn't really an advantage in terms of computation time.)
The method
a_maximal_chain
can be generalized to allow this. Currently it only gives some maximal chain, but we can easily obtain a maximal chain for each facet. This allows computing a unique inequality for each facet (in the non-degenerate case), given the V-representation.a_maximal_chain
also allows obtaining the equations.Given the H-representation we might as well be lazy and just use
CombinatorialPolyhedron.polar
for this.I'm not exactly sure what you mean by
allow_degeneration
. This is what I think for the case that the V-representation is given:d
be the dimension of the affine hull of the V-representation, eitherd=0
or for each facet, the corresponding V-representation objects must have affine hull dimension less thand
allow_degeneration=False
thand
must be the dimension of theCombinatorialPolyhedron
and the objects corresponding to the facets must have affine hull dimensiond-1
and those affine hulls must be unique for each facetd-1
dimensional affine hull defines a unique inequality, those inequalities are the computed H-representationallow_degeneration=True
the remaining facets must have degenerated to a subset of some proper facetallow_degeneration=False
the incidence matrix (of the given V-representation and the computed H-representation) must be the same as the incidence matrix of the combinatorial polyhedronIt all depends on how much degeneration we allow. Another approach is that
allow_degeneration=True
only allows facets to collaps. So for any face of the combinatorial polyhedron the affine hull dimension of the given V-representation must be as expected.