Sage: Ticket #31799: From CombinatorialPolyhedron and H-representation to Polyhedron (with double description)
https://trac.sagemath.org/ticket/31799
<p>
Given an (abstract) <code>CombinatorialPolyhedron</code> such that <strong>at least one</strong> of H-representation and V-representation are labeled geometrically, the new method <code>CombinatorialPolyhedron.as_polyhedron</code> constructs a geometric polyhedron.
</p>
<p>
If <code>check=True</code> (default), it checks that the result is OK.
</p>
<p>
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:
</p>
<ul><li>if both representations are geometric, just pass them to the polyhedron constructor (<a class="new ticket" href="https://trac.sagemath.org/ticket/26366" title="enhancement: Polyhedron constructors: minimal vs. non-minimal input ... (new)">#26366</a>)
</li><li>if only one representation is geometric, reconstruct the other one from the incidences by equation solving.
</li></ul><p>
Ideally, an optional argument <code>allow_degeneration</code> would allow that the given representation data actually gives a degeneration of the given combinatorial polyhedron.
</p>
<p>
In the context of <a class="new ticket" href="https://trac.sagemath.org/ticket/31803" title="enhancement: Make CombinatorialPolyhedron an element class, define morphisms of ... (new)">#31803</a>, this would be a morphism.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/31799
Trac 1.1.6mkoeppeSun, 09 May 2021 02:47:22 GMTdescription changed
https://trac.sagemath.org/ticket/31799#comment:1
https://trac.sagemath.org/ticket/31799#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/31799?action=diff&version=1">diff</a>)
</li>
</ul>
TicketmkoeppeSun, 09 May 2021 18:19:46 GMTdescription changed
https://trac.sagemath.org/ticket/31799#comment:2
https://trac.sagemath.org/ticket/31799#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/31799?action=diff&version=2">diff</a>)
</li>
</ul>
Ticketgh-kliemMon, 10 May 2021 10:00:15 GMT
https://trac.sagemath.org/ticket/31799#comment:3
https://trac.sagemath.org/ticket/31799#comment:3
<p>
It only seems to make sense for those backends that allow initialization from both V-representation and H-representation.
</p>
<p>
(Normaliz somehow allows precomputed data, but it appears that initializing from precomputed data isn't really an advantage in terms of computation time.)
</p>
<p>
The method <code>a_maximal_chain</code> 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. <code>a_maximal_chain</code> also allows obtaining the equations.
</p>
<p>
Given the H-representation we might as well be lazy and just use <code>CombinatorialPolyhedron.polar</code> for this.
</p>
<p>
I'm not exactly sure what you mean by <code>allow_degeneration</code>. This is what I think for the case that the V-representation is given:
</p>
<ul><li>let <code>d</code> be the dimension of the affine hull of the V-representation, either <code>d=0</code> or for each facet, the corresponding V-representation objects must have affine hull dimension less than <code>d</code>
</li><li>if <code>allow_degeneration=False</code> than <code>d</code> must be the dimension of the <code>CombinatorialPolyhedron</code> and the objects corresponding to the facets must have affine hull dimension <code>d-1</code> and those affine hulls must be unique for each facet
</li><li>a maximal chain corresponding to a <code>d-1</code> dimensional affine hull defines a unique inequality, those inequalities are the computed H-representation
</li><li>if <code>allow_degeneration=True</code> the remaining facets must have degenerated to a subset of some proper facet
</li><li>the slack matrix (of the given V-representation and the computed H-representation) must always be non-negative
</li><li>if <code>allow_degeneration=False</code> 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
</li></ul><p>
It all depends on how much degeneration we allow. Another approach is that <code>allow_degeneration=True</code> 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.
</p>
TicketmkoeppeMon, 10 May 2021 17:15:27 GMT
https://trac.sagemath.org/ticket/31799#comment:4
https://trac.sagemath.org/ticket/31799#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/31799#comment:3" title="Comment 3">gh-kliem</a>:
</p>
<blockquote class="citation">
<p>
It only seems to make sense for those backends that allow initialization from both V-representation and H-representation.
</p>
</blockquote>
<p>
Yes, that's right. For the moment I am fine with just creating polyhedra in the <code>field</code> backend. In fact, my main application will be for parametric polyhedra (where the coefficient field is a <a class="ext-link" href="https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/cutgeneratingfunctionology/igp/parametric.sage#L68"><span class="icon"></span>ParametricRealField</a>).
</p>
<blockquote class="citation">
<p>
(Normaliz somehow allows precomputed data, but it appears that initializing from precomputed data isn't really an advantage in terms of computation time.)
</p>
</blockquote>
<p>
Hopefully at some point this can be improved - but it's not the main direction of this ticket.
</p>
<blockquote class="citation">
<p>
The method <code>a_maximal_chain</code> 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. <code>a_maximal_chain</code> also allows obtaining the equations.
</p>
<p>
Given the H-representation we might as well be lazy and just use <code>CombinatorialPolyhedron.polar</code> for this.
</p>
</blockquote>
<p>
Sounds great!
</p>
TicketmkoeppeMon, 10 May 2021 17:37:36 GMT
https://trac.sagemath.org/ticket/31799#comment:5
https://trac.sagemath.org/ticket/31799#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/31799#comment:3" title="Comment 3">gh-kliem</a>:
</p>
<blockquote class="citation">
<p>
I'm not exactly sure what you mean by <code>allow_degeneration</code>. This is what I think for the case that the V-representation is given: [...]
</p>
</blockquote>
<blockquote class="citation">
<ul><li>the slack matrix (of the given V-representation and the computed H-representation) must always be non-negative
</li></ul></blockquote>
<p>
Yes
</p>
<blockquote class="citation">
<ul><li>if <code>allow_degeneration=False</code> 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
</li></ul></blockquote>
<p>
Yes, and for <code>allow_degeneration=True</code>, we would just drop this requirement, I think.
</p>
<blockquote class="citation">
<p>
It all depends on how much degeneration we allow.
</p>
</blockquote>
<p>
Let's consider the generalized permutahedron as a model. I would like to include its degenerations in full generality.
</p>
<p>
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.
</p>
Ticketgh-kliemMon, 10 May 2021 19:46:13 GMT
https://trac.sagemath.org/ticket/31799#comment:6
https://trac.sagemath.org/ticket/31799#comment:6
<p>
In light of <a class="new ticket" href="https://trac.sagemath.org/ticket/31801" title="enhancement: PolyhedronFace.as_polyhedron: Provide double description to backends ... (new)">#31801</a> we should probably add an optional argument <code>verify</code> with default <code>True</code>.
</p>
Ticketgh-kliemMon, 10 May 2021 20:58:18 GMT
https://trac.sagemath.org/ticket/31799#comment:7
https://trac.sagemath.org/ticket/31799#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/31799#comment:5" title="Comment 5">mkoeppe</a>:
</p>
<blockquote class="citation">
<p>
[...]
</p>
<p>
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.
</p>
</blockquote>
<p>
Ah, ok. From my intuition (which might be wrong as well), the following happens at a degeneration map:
</p>
<ul><li>There exists a list of disjoint faces, which get contracted (so only one vertex remains for each of those faces).
</li><li>First step is to contract the vertices according to the map and apply a bitwise OR to the (old) coatom incidences.
</li><li>The new coatoms are the inclusion maximal coatoms.
</li><li>Each old coatom should still define a face (I think this holds automatically).
</li></ul><p>
What needs to be checked:
</p>
<ul><li>Whether each equivalence class of vertices corresponds to a face (compute the join of those atoms).
</li></ul><p>
If this is correct, this ticket should depend on <a class="closed ticket" href="https://trac.sagemath.org/ticket/29683" title="enhancement: "look up" a face in the face lattice of a polyhedron (closed: fixed)">#29683</a>.
</p>
<p>
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).
</p>
<p>
Do we allow degenerations that might be obtained by iteratively degenerating? Might be a bit harder to check.
</p>
Ticketgh-kliemWed, 12 May 2021 14:15:24 GMTdependencies set
https://trac.sagemath.org/ticket/31799#comment:8
https://trac.sagemath.org/ticket/31799#comment:8
<ul>
<li><strong>dependencies</strong>
set to <em>#31823</em>
</li>
</ul>
TicketmkoeppeWed, 12 May 2021 19:49:03 GMT
https://trac.sagemath.org/ticket/31799#comment:9
https://trac.sagemath.org/ticket/31799#comment:9
<p>
As for designing the interface, I would like to introduce a method <code>CombinatorialPolyhedra.hom</code> to construct the morphism
(as you suggest, with a <code>verify</code> (or <code>check</code>?) keyword argument)
</p>
Ticketgh-kliemWed, 12 May 2021 19:53:41 GMT
https://trac.sagemath.org/ticket/31799#comment:10
https://trac.sagemath.org/ticket/31799#comment:10
<p>
Should be a <code>check</code> keyword according to <code>git grep</code>. <code>verify</code> is used (almost) exclusively for <code>sage_input</code>.
</p>
TicketmkoeppeWed, 12 May 2021 20:09:12 GMT
https://trac.sagemath.org/ticket/31799#comment:11
https://trac.sagemath.org/ticket/31799#comment:11
<p>
So something like this:
</p>
<pre class="wiki">class CombinatorialPolyhedra(UniqueRepresentation, Parent):
...
def hom(self, Vrep_dict, codomain=None, check=True, category=None):
</pre>
TicketmkoeppeWed, 12 May 2021 20:11:30 GMT
https://trac.sagemath.org/ticket/31799#comment:12
https://trac.sagemath.org/ticket/31799#comment:12
<p>
... it should return an instance of a class similar to <code>SimplicialComplexMorphism</code>
</p>
TicketmkoeppeFri, 14 May 2021 16:51:11 GMT
https://trac.sagemath.org/ticket/31799#comment:13
https://trac.sagemath.org/ticket/31799#comment:13
<p>
A skeleton of the classes to implement morphisms is now on <a class="new ticket" href="https://trac.sagemath.org/ticket/31803" title="enhancement: Make CombinatorialPolyhedron an element class, define morphisms of ... (new)">#31803</a>.
</p>
TicketmkoeppeWed, 26 May 2021 00:07:23 GMTdescription changed
https://trac.sagemath.org/ticket/31799#comment:14
https://trac.sagemath.org/ticket/31799#comment:14
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/31799?action=diff&version=14">diff</a>)
</li>
</ul>
TicketmkoeppeWed, 26 May 2021 05:59:02 GMTdependencies changed
https://trac.sagemath.org/ticket/31799#comment:15
https://trac.sagemath.org/ticket/31799#comment:15
<ul>
<li><strong>dependencies</strong>
changed from <em>#31823</em> to <em>#31823, #26366</em>
</li>
</ul>
TicketmkoeppeWed, 26 May 2021 06:30:52 GMTbranch set
https://trac.sagemath.org/ticket/31799#comment:16
https://trac.sagemath.org/ticket/31799#comment:16
<ul>
<li><strong>branch</strong>
set to <em>u/mkoeppe/from_combinatorialpolyhedron_and_h_representation_to_polyhedron__with_double_description_</em>
</li>
</ul>
TicketmkoeppeWed, 26 May 2021 06:34:22 GMTdescription changed; commit set
https://trac.sagemath.org/ticket/31799#comment:17
https://trac.sagemath.org/ticket/31799#comment:17
<ul>
<li><strong>commit</strong>
set to <em>789eadafc5807c003ccf7f8b0611b68760da2d3a</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/31799?action=diff&version=17">diff</a>)
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=05fef94a5c8e3317daae7ffc996ff4f87e0443ac"><span class="icon"></span>05fef94</a></td><td><code>src/sage/geometry/polyhedron/constructor.py: Add more constructors</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=624ec2b5edff0b13358fba4b9af5f1cb70a49bdf"><span class="icon"></span>624ec2b</a></td><td><code>Merge #26366</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=789eadafc5807c003ccf7f8b0611b68760da2d3a"><span class="icon"></span>789eada</a></td><td><code>CombinatorialPolyhedron.as_polyhedron: New</code>
</td></tr></table>
TicketmkoeppeMon, 19 Jul 2021 01:16:42 GMTmilestone changed
https://trac.sagemath.org/ticket/31799#comment:18
https://trac.sagemath.org/ticket/31799#comment:18
<ul>
<li><strong>milestone</strong>
changed from <em>sage-9.4</em> to <em>sage-9.5</em>
</li>
</ul>
TicketmkoeppeTue, 14 Dec 2021 02:04:49 GMTmilestone changed
https://trac.sagemath.org/ticket/31799#comment:19
https://trac.sagemath.org/ticket/31799#comment:19
<ul>
<li><strong>milestone</strong>
changed from <em>sage-9.5</em> to <em>sage-9.6</em>
</li>
</ul>
Ticket