Inverse function for gale_transform

[kliem]

One can obtain a gale diagram from a polyhedron. Some interesting examples of polyhedra are obtained by the reverse approach.

We implement a method that converts a gale diagram to a Polyhedron.

This is a preparation for adding polytopes to the library obtained from the Gale diagram (e.g. #27728).

CC: @jplab @LaisRast @yuan-zhou

Component: geometry

Keywords: polytopes, gale transform

Author: Jonathan Kliem

Branch/Commit: b6898dd

Reviewer: Jean-Philippe Labbé

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

[kliem]

New commits:

baaa735

implement function to convert from gale transform to polytope

[kliem]

Commit: baaa735

[kliem]

Branch: public/29065

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b32c073

various improvements

[sagetrac-git]

Changed commit from baaa735 to b32c073

[sagetrac-git]

Changed commit from b32c073 to 8f91299

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8f91299

do not echolonize kernel matrix

[LaisRast]

comment:5

Small remarks:

• Typos:

-    The vectors are scalled automatically such that they add up to zero.
+    The vectors are scaled automatically such that they add up to zero.

-        # The vectors of our gale transform shall add up to one.
+        # The vectors of our gale transform shall add up to zero.

• Maybe explain why you want the sum of all vectors to be zero. Something like "so that the right kernel of vectors has the one vector in it".

[sagetrac-git]

Changed commit from 8f91299 to 251e9f5

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

251e9f5

better documentation

[jplab]

comment:7

Here are some comments:

• I would name the function gale_transform_to_polytope since there is no unbounded case here.

def gale_transform_to_polyhedron(vectors, base_ring=None, backend=None):
    r"""
-    Return the polytope from a (linear) gale transform.
+    Return the polytope associated to the list of vectors forming a Gale transform.

    This function is the inverse of
    :meth:`~sage.geometry.polyhedron.base.Polyhedron_base.gale_transform`
-    up to projective isomorphism.
+    up to projective transformation.

+    The vectors are scaled automatically such that they add up to zero.

This needs to be more clear. Is it: The _vertices_ of the polytope are scaled so that the sum of their coordinates is zero? I believe not, right? Then it should say that the centroid (which is what you mean, I'm pretty sure) should be the origin.

I think that the following sentence should be changed to reflect what the function does internally (if it is not the case, you mention in the comments in the code that you do it, this should be mentioned here too!).

+    The function is much faster and gives nicer representation if this
+    is already the case.

+    INPUT:
+
-    - ``vectors`` -- the vectors of the gale transform
+    - ``vectors`` -- the ordered vectors of the Gale transform

Please use the suggested format when using default values for optional parameters:

+    - ``base_ring`` -- (optional) the base ring to be used for the construction
+
+    - ``backend`` -- (optional) the backend to use to create the polytope
+

gale transform -> Gale transform (but not in names of functions...)

straight forward -> straightforward

[kliem]

comment:8

This comment is totally cryptic to me. Should I change the format? To what? There is tons of different styles for this all over the place.

The coding conventions suggest the following:

- ``base_ring`` -- string (default: `None`); the base ring to be used for the construction

Why is the order of the vectors of importance?

Replying to @jplab:

Please use the suggested format when using default values for optional parameters:

+    - ``base_ring`` -- (optional) the base ring to be used for the construction
+
+    - ``backend`` -- (optional) the backend to use to create the polytope
+

gale transform -> Gale transform (but not in names of functions...)

straight forward -> straightforward

[kliem]

New commits:

d4868b8	implement function to convert from gale transform to polytope
1e34f2a	various improvements
cc8f79a	do not echolonize kernel matrix
35351b4	better documentation
f833ccc	fixed failing doctest
e541471	improved function name and documentation

[kliem]

Changed commit from 251e9f5 to e541471

[kliem]

Changed branch from public/29065 to public/29065-reb

[jplab]

comment:10

Replying to @kliem:

This comment is totally cryptic to me. Should I change the format? To what? There is tons of different styles for this all over the place.

The coding conventions suggest the following:

- ``base_ring`` -- string (default: `None`); the base ring to be used for the construction

I like the above convention, yes.

Why is the order of the vectors of importance?

Essentially, to make things clear and smooth, it is practical to talk about a "labeled" set of vector, where the set of labels has a total order a.k.a. essentially numbered from 1 to k.

In practice, when one uses Gale duality, to go from primal to dual notions and vice-versa, it is important to have a precise ground set in order to do the translations: complementation should be well-defined, and as soon as you get into the oriented matroid business, it is important to get the signs right... This is why it is a soothing measure to mention here in the first line of the documentation that we do care that this is an (ordered) list of vectors.

This will make our life easier when explaining/doing things.

[jplab]

comment:11

About this, we should also add a reference to another book.

I suggest the Triangulations book of De Loera, Rambau, Santos. Definition 2.5.1 and Definition 4.1.35.

Essentially, this function is not necessarily to get a polytope, right?

Or does it really check for the polytopality property?

I see the possibility here to split into two functions...

[sagetrac-git]

Changed commit from e541471 to 3a909c1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5bfb0bb	added another reference
3a909c1	split function in two functions

[jplab]

comment:18

Tiny things:

+        sage: gale_transform_to_polytope(
+        ....:     [(1,1), (-1,-1), (1,0),
+        ....:      (-1,0), (1,-1), (-2,1)],
+        ....:     backend='cdd', base_ring=RDF)
+        A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 6 vertices

I know that cdd is the only backend handling RDF, but perhaps it would be good to still check the backend like the example just before...

Question: is this test equivalent to the fact that it is not the correct polytope:

+    if not P.n_vertices() == len(vertices):
+        raise ValueError("the gale transform does not correspond to a polytope")

It would be good to give a reference for that line in the code in a comment. I want to make sure to catch this error if and only if the thing go wrong (so that other types of errors are not hidden by that failing/passing like it happened a lot in polyhedron stuff...).

In gale_transform_to_primal, be careful in describing _all_ the details properly. We do not assume that the centroid of the vectors to be the origin, but rather

-    We assume the centroid of the (input) vectors to be the origin.
-    We stack ``Matrix(vectors)`` by a row of ones.
-    The right kernel of this is the dual point configuration.
+    If the centroid of the (input) vectors is not the origin, we do an appropriate transformation to make it so.
+    We add a row of ones on top of ``Matrix(vectors)``.
+    The right kernel of this larger matrix is the dual configuration space, and a basis of this space provides the dual point configuration.

Then paragraph 3 and 4 of the algorithm are a bit hard to parse... Perhaps rework them a bit?

[kliem]

Changed branch from public/29065-reb to public/29065-reb2

[kliem]

Changed commit from 55f62a8 to 948d992

[kliem]

Last 10 new commits:

c7b0446	various improvements
2f7aa65	do not echolonize kernel matrix
c2e1d33	better documentation
49a2e23	fixed failing doctest
988f81f	improved function name and documentation
e0e975d	added another reference
7aaa768	split function in two functions
b9f3860	improved documentation
0691033	tiny improvement of doctests
948d992	error message for non-spanning gale transform; improved documentation

[jplab]

comment:21

You will hate me for this, but "centroid" is the wrong term.

What you mean is "center" (the centroid method is not implemented yet, see https://ask.sagemath.org/question/8092/compute-the-centroid-of-a-polytope/ ... which is also to be implemented ...Sighhhhhh).

One small thing:

-    convex if and only if every hyperplane contains at least two vectors of
+    convex and if and only if every hyperplane contains at least two vectors of

Otherwise, looks very good!

[sagetrac-git]

Changed commit from 948d992 to b6898dd

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b6898dd

centroid -> center; small correction

[kliem]

comment:23

:-)

[jplab]

comment:24

I'm working on #27728 which depends on this ticket, and I might have some more feedback about the functions. Let's wait for that and the bots.

[mkoeppe]

comment:25

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[jplab]

comment:26

Ok, looks good. If there are more modifications on this function, they can be addressed in #27728.

[vbraun]

Changed branch from public/29065-reb2 to b6898dd