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

[mkoeppe]

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 (Polyhedron constructors: minimal vs. non-minimal input representations; input both Vrep and Hrep #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.

Depends on #31823
Depends on #26366

CC: @kliem @yuan-zhou @jplab

Component: geometry

Branch/Commit: u/mkoeppe/from_combinatorialpolyhedron_and_h_representation_to_polyhedron__with_double_description_ @ 789eada

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

[kliem]

comment:3

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.

[mkoeppe]

comment:4

Replying to @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!

[mkoeppe]

comment:5

Replying to @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.

[kliem]

comment:6

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

[kliem]

comment:7

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.

[kliem]

Dependencies: #31823

[mkoeppe]

comment:9

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)

[kliem]

comment:10

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

[mkoeppe]

comment:11

So something like this:

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

[mkoeppe]

comment:12

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

[mkoeppe]

comment:13

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

[mkoeppe]

Changed dependencies from #31823 to #31823, #26366

[mkoeppe]

Branch: u/mkoeppe/from_combinatorialpolyhedron_and_h_representation_to_polyhedron__with_double_description_

[mkoeppe]

Commit: 789eada

[mkoeppe]

New commits:

05fef94	src/sage/geometry/polyhedron/constructor.py: Add more constructors
624ec2b	Merge #26366
789eada	CombinatorialPolyhedron.as_polyhedron: New