Opened 7 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.5
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:

Status badges

Description (last modified by 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 (#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 (18)

comment:1 Changed 7 months ago by mkoeppe

  • Description modified (diff)

comment:2 Changed 7 months ago by mkoeppe

  • Description modified (diff)

comment:3 follow-ups: Changed 7 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 7 months ago by mkoeppe

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

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

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

Last edited 7 months ago by gh-kliem (previous) (diff)

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

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

  • Dependencies set to #31823

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

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

comment:13 Changed 7 months ago by mkoeppe

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

comment:14 Changed 6 months ago by mkoeppe

  • Description modified (diff)

comment:15 Changed 6 months ago by mkoeppe

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

comment:16 Changed 6 months ago by mkoeppe

  • Branch set to u/mkoeppe/from_combinatorialpolyhedron_and_h_representation_to_polyhedron__with_double_description_

comment:17 Changed 6 months ago by mkoeppe

  • Commit set to 789eadafc5807c003ccf7f8b0611b68760da2d3a
  • Description modified (diff)

New commits:

05fef94src/sage/geometry/polyhedron/constructor.py: Add more constructors
624ec2bMerge #26366
789eadaCombinatorialPolyhedron.as_polyhedron: New

comment:18 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5
Note: See TracTickets for help on using tickets.