Opened 9 months ago

From CombinatorialPolyhedron and H-representation to Polyhedron (with double description)

Reported by: Owned by: mkoeppe major sage-9.6 geometry gh-kliem, yzh, jipilab N/A u/mkoeppe/from_combinatorialpolyhedron_and_h_representation_to_polyhedron__with_double_description_ 789eadafc5807c003ccf7f8b0611b68760da2d3a #31823, #26366

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.

comment:1 Changed 9 months ago by mkoeppe

• Description modified (diff)

comment:2 Changed 9 months ago by mkoeppe

• Description modified (diff)

comment:3 follow-ups: ↓ 4 ↓ 5 Changed 9 months ago by gh-kliem

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:

• let d be the dimension of the affine hull of the V-representation, either d=0 or for each facet, the corresponding V-representation objects must have affine hull dimension less than d
• if allow_degeneration=False than d must be the dimension of the CombinatorialPolyhedron and the objects corresponding to the facets must have affine hull dimension d-1 and those affine hulls must be unique for each facet
• a maximal chain corresponding to a d-1 dimensional affine hull defines a unique inequality, those inequalities are the computed H-representation
• if allow_degeneration=True the remaining facets must have degenerated to a subset of some proper facet
• the slack matrix (of the given V-representation and the computed H-representation) must always be non-negative
• 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

It 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.

comment:4 in reply to: ↑ 3 Changed 9 months ago by mkoeppe

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 9 months ago by mkoeppe

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 9 months ago by gh-kliem

In light of #31801 we should probably add add an optional argument verify with default True.

Version 0, edited 9 months ago by gh-kliem (next)

comment:7 in reply to: ↑ 5 Changed 9 months ago by gh-kliem

[...]

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 9 months ago by gh-kliem

• Dependencies set to #31823

comment:9 Changed 9 months ago by mkoeppe

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 9 months ago by gh-kliem

Should be a check keyword according to git grep. verify is used (almost) exclusively for sage_input.

comment:11 Changed 9 months ago by mkoeppe

So something like this:

class CombinatorialPolyhedra(UniqueRepresentation, Parent):
...
def hom(self, Vrep_dict, codomain=None, check=True, category=None):

comment:12 Changed 9 months ago by mkoeppe

... it should return an instance of a class similar to SimplicialComplexMorphism

comment:13 Changed 9 months ago by mkoeppe

A skeleton of the classes to implement morphisms is now on #31803.

comment:14 Changed 8 months ago by mkoeppe

• Description modified (diff)

comment:15 Changed 8 months ago by mkoeppe

• Dependencies changed from #31823 to #31823, #26366

comment:16 Changed 8 months ago by mkoeppe

• Branch set to u/mkoeppe/from_combinatorialpolyhedron_and_h_representation_to_polyhedron__with_double_description_

comment:17 Changed 8 months ago by mkoeppe

• Description modified (diff)

New commits: