Opened 3 years ago

Closed 3 years ago

# Inverse function for `gale_transform`

Reported by: Owned by: gh-kliem major sage-9.1 geometry polytopes, gale transform Jean-Philippe Labbé, Laith Rastanawi, Yuan Zhou Jonathan Kliem Jean-Philippe Labbé N/A b6898dd b6898dd2c7afae73958f4d3daaab063b1e751337

### Description

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

### comment:1 Changed 3 years ago by gh-kliem

Branch: → public/29065 → baaa7350520c1e65a66a4ac7c60fb66ce5b3b147 new → needs_review

New commits:

 ​baaa735 `implement function to convert from gale transform to polytope`

### comment:2 Changed 3 years ago by git

Commit: baaa7350520c1e65a66a4ac7c60fb66ce5b3b147 → b32c0735232e300bbe02806ef255ef38702a8d31

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

 ​b32c073 `various improvements`

### comment:3 Changed 3 years ago by git

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

 ​8f91299 `do not echolonize kernel matrix`

### comment:5 Changed 3 years ago by Laith Rastanawi

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".
Last edited 3 years ago by Laith Rastanawi (previous) (diff)

### comment:6 Changed 3 years ago by git

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

 ​251e9f5 `better documentation`

### comment:7 follow-up:  8 Changed 3 years ago by Jean-Philippe Labbé

Status: needs_review → needs_work

• 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
```
```+    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

### comment:8 in reply to:  7 ; follow-up:  10 Changed 3 years ago by gh-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
```

Why is the order of the vectors of importance?

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

### comment:9 Changed 3 years ago by gh-kliem

Branch: public/29065 → public/29065-reb 251e9f51633e46c6b9d102a160243cca818111d1 → e54147184c209d81990fe7bfb7f4816ca2fc27a5 needs_work → needs_review

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`

### comment:10 in reply to:  8 Changed 3 years ago by Jean-Philippe Labbé

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.

Last edited 3 years ago by Jean-Philippe Labbé (previous) (diff)

### comment:11 Changed 3 years ago by Jean-Philippe Labbé

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

### comment:12 Changed 3 years ago by Jean-Philippe Labbé

Status: needs_review → needs_work

### comment:13 Changed 3 years ago by git

Commit: e54147184c209d81990fe7bfb7f4816ca2fc27a5 → 3a909c1afa6b6d472301e00bfd4069e9abe090a2

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

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

### comment:14 Changed 3 years ago by gh-kliem

Status: needs_work → needs_review

New commits:

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

New commits:

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

### comment:15 Changed 3 years ago by Jean-Philippe Labbé

Reviewers: → Jean-Philippe Labbé needs_review → needs_work

Tiny things:

```+        .. SEEALSO::
+
-            :func`~sage.geometry.polyhedron.library.gale_transform_to_polyhedron`.
+            :func`~sage.geometry.polyhedron.library.gale_transform_to_polytope`.
```
```-    OUTPUT: An ordered point confuration as list of vectors.
+    OUTPUT: An ordered point configuration as list of vectors.
```
```-    One can also specify the backend to be used interally::
+    One can also specify the backend to be used internally::
```
```-    The input vectors are checked for being totally cyclic::
+    The input vectors should be totally cyclic::
```
```-        # of the polyhedron. So dehomogenization is straight forward.
+        # of the polyhedron. So dehomogenization is straightforward.
```

I find the "algorithm" part a bit hard to understand, but that might just be me. I will see if I can come up with an suggestion of improvement.

### comment:16 Changed 3 years ago by git

Commit: 3a909c1afa6b6d472301e00bfd4069e9abe090a2 → 55f62a8936590627672cd3f261e1abbc95abcbf2

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

 ​55f62a8 `improved documentation`

### comment:17 Changed 3 years ago by gh-kliem

Status: needs_work → needs_review

I hope this is better now. I completely rewrote the algorithm part.

### comment:18 Changed 3 years ago by Jean-Philippe Labbé

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?

### comment:19 Changed 3 years ago by Jean-Philippe Labbé

Status: needs_review → needs_work

### comment:20 Changed 3 years ago by gh-kliem

Branch: public/29065-reb → public/29065-reb2 55f62a8936590627672cd3f261e1abbc95abcbf2 → 948d9920d25e1ccc10c1471c402d8dbe02326f91 needs_work → needs_review

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`

### comment:21 Changed 3 years ago by Jean-Philippe Labbé

Status: needs_review → needs_work

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!

### comment:22 Changed 3 years ago by git

Commit: 948d9920d25e1ccc10c1471c402d8dbe02326f91 → b6898dd2c7afae73958f4d3daaab063b1e751337

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

 ​b6898dd `centroid -> center; small correction`

### comment:23 Changed 3 years ago by gh-kliem

Status: needs_work → needs_review

:-)

### comment:24 Changed 3 years ago by Jean-Philippe Labbé

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.

### comment:25 Changed 3 years ago by Matthias Köppe

Milestone: sage-9.1 → sage-9.2

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.

### comment:26 Changed 3 years ago by Jean-Philippe Labbé

Status: needs_review → positive_review

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

### comment:27 Changed 3 years ago by Volker Braun

Branch: public/29065-reb2 → b6898dd2c7afae73958f4d3daaab063b1e751337 → fixed positive_review → closed

### comment:28 Changed 3 years ago by Matthias Köppe

Milestone: sage-9.2 → sage-9.1
Note: See TracTickets for help on using tickets.