Sage: Ticket #27534: Implement Lawrence extension for polytopes
https://trac.sagemath.org/ticket/27534
<p>
Adding the following methods to base.py:
</p>
<ul><li><code>lawrence_extension(self, v)</code>:
Return the Lawrence extension of <code>self</code> on the point <code>v</code>.
</li><li><code>lawrence_polytope(self)</code>:
Return the Lawrence polytope of <code>self</code>.
</li><li><code>is_lawrence_polytope(self)</code>:
Return <code>true</code> if <code>self</code> is a Lawrence polytope.
</li></ul><p>
for definitions, see
Section 6.6 of Lectures on Polytopes, Günter M. Ziegler, [Zie2007]
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/27534
Trac 1.2Laith RastanawiFri, 22 Mar 2019 15:34:01 GMTcommit, branch set
https://trac.sagemath.org/ticket/27534#comment:1
https://trac.sagemath.org/ticket/27534#comment:1
<ul>
<li><strong>commit</strong>
set to <em>a7849b3ecea4f36f7233940ee6d18a0af943013c</em>
</li>
<li><strong>branch</strong>
set to <em>public/27534</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=a7849b3ecea4f36f7233940ee6d18a0af943013c"><span class="icon"></span>a7849b3</a></td><td><code>adding Lawrence polytope</code>
</td></tr></table>
TicketLaith RastanawiFri, 22 Mar 2019 15:48:50 GMTstatus changed
https://trac.sagemath.org/ticket/27534#comment:2
https://trac.sagemath.org/ticket/27534#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
Ticketgh-kliemFri, 22 Mar 2019 20:40:45 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/27534#comment:3
https://trac.sagemath.org/ticket/27534#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jonathan Kliem</em>
</li>
</ul>
<p>
A few small comments.
</p>
<ol><li>Single quotes (or whatever the name of those things is) is for latex, double for code-style. There is at least one place (using <code>self</code>), where this is inconsistent.
</li><li><code>The Lawrence extension of P</code>, what is P? How about <code>The Lawrence extension of a polytope P</code>?
</li><li>A comment I just received myself: "These bullet points for <code>INPUT:</code> do not, by general Sage convention, end in a period/full-stop."
</li><li>It seems to me that the requirement of being full dimensional is not necessary. Instead one can require 0 to be contained, if its not full dimensional. If a polytope <code>P</code> satisfies "ax = 0" for all x in P, then the lawrence extension will just satisfie "(a,0)x = 0". I.e. if all hyperplanes containing P are linear, then the Lawrence extension will be contained in the "same" hyperplanes. I propose something like:
<div class="wiki-code"><div class="code"><pre><span class="gd">- if not self.is_full_dimensional():
- raise NotImplementedError("`self` must be full dimensional")
</span><span class="gi">+ if not self.is_full_dimensional():
+ if not self.contains([0]*self.ambient_dim()):
+ raise NotImplementedError("``self`` must be full-dimensional or contain the origin, try ``self.translation``")
</span></pre></div></div></li></ol><p>
Then, one can add an example that explains how to proceed in case of a not full-dimensional polytope:
</p>
<pre class="wiki">sage: P = polytopes.permutahedron(4)
sage: Q = lawrence_polytope(P)
Traceback (most recent call last):
...
NotImplementedError: ``self`` must be full-dimensional or contain the origin, try ``self.translation``
sage: T = P.translation(-vector(P.vertices()[0]))
sage: Q = lawrence_polytope(T)
sage: Q
A 26-dimensional polyhedron in ZZ^28 defined as the convex hull of 47 vertices
</pre><p>
Maybe add another example like this to the Lawrence extension (maybe <code>Birkhoff_polytope(3)</code>).
</p>
<ol start="5"><li>I find too many commands in one line hard to read:
<div class="wiki-code"><div class="code"><pre><span class="gd">- sage: P = polytopes.cube(); Q = P.lawrence_polytope(); Q.is_lawrence_polytope()
- True
</span><span class="gi">+ sage: P = polytopes.cube()
+ sage: Q = P.lawrence_polytope()
+ sage: Q.is_lawrence_polytope()
+ True
</span></pre></div></div></li><li>I would use <code>True</code> instead of <code>true</code>.
</li><li>You never use <code>d = self.dim()</code>.
</li></ol>
TicketLaith RastanawiSun, 24 Mar 2019 00:32:34 GMT
https://trac.sagemath.org/ticket/27534#comment:4
https://trac.sagemath.org/ticket/27534#comment:4
<p>
Thanks for your comments.
</p>
<p>
The functions need to be rewritten entirely: for instance, my function <code>lawrence_polytope</code> does produce a Lawrence polytope, but not <strong>the</strong> Lawrence polytope of <code>self</code> according to the usual definitions (there are two different definitions for it).
</p>
<p>
I will come back to this ticket later and fix everything.
</p>
Ticketgh-kliemSun, 24 Mar 2019 15:38:18 GMT
https://trac.sagemath.org/ticket/27534#comment:5
https://trac.sagemath.org/ticket/27534#comment:5
<p>
One more remark.
</p>
<p>
<code>is_lawrence_polytope</code> is very slow in cases, where the polytope does not have few vertices. Try checking this for <code>permutahedron(6)</code>.
</p>
<p>
Instead of computing the Gale-transform, one could just grap the information from the facets.
</p>
<ol><li>Create a list of vertices <code>V</code>.
</li><li>Iterate through all facets <code>F</code> containing exactly <code>n-1</code> vertices.
</li><li>Remove the vertex not contained in <code>F</code> from <code>V</code> (this vertex "is" the origin in the Gale transform).
</li><li>Iterate through all facets <code>F</code> containing exactly <code>n-2</code> vertices.
</li><li>Let v_1,v_2 not be in <code>F</code>. If v_1 and v_2 in <code>V</code>, remove them.
</li></ol><p>
If at the end of this <code>V</code> is empty, the Gale diagram is centrally symmetric. If not, then it is not.
</p>
TicketJean-Philippe LabbéSat, 30 Mar 2019 11:27:23 GMT
https://trac.sagemath.org/ticket/27534#comment:6
https://trac.sagemath.org/ticket/27534#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/27534#comment:5" title="Comment 5">gh-kliem</a>:
</p>
<blockquote class="citation">
<p>
One more remark.
</p>
<p>
<code>is_lawrence_polytope</code> is very slow in cases, where the polytope does not have few vertices. Try checking this for <code>permutahedron(6)</code>.
</p>
</blockquote>
<p>
It is hard to have an algorithm that gets faster as the input gets larger!
</p>
<p>
In spite of that, yes, it might not be optimized, but I would not go into intricate implementation of the function unless there is yet a known use case.
</p>
<p>
One suggestion:
</p>
<p>
Perles' example of a non-rational polytope uses lawrence extension to be constructed. It would be nice to add the example to the library of polytopes (either using lawrence extension or just hard-coding the vertices. Or even better, hard-coding the vertices and in the test of the function for the polytope, construct the polytope using lawrence extension and check that it is really combinatorially isomorphic.
</p>
TicketJean-Philippe LabbéSat, 30 Mar 2019 11:29:14 GMT
https://trac.sagemath.org/ticket/27534#comment:7
https://trac.sagemath.org/ticket/27534#comment:7
<p>
The Title of the ticket should be more precise about what the ticket provides.
</p>
<p>
In order to make this ticket more accessible, it would be nice to have related keywords: polytopes and lawrence extension.
</p>
Ticketgh-kliemSat, 30 Mar 2019 15:10:47 GMT
https://trac.sagemath.org/ticket/27534#comment:8
https://trac.sagemath.org/ticket/27534#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/27534#comment:6" title="Comment 6">jipilab</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/27534#comment:5" title="Comment 5">gh-kliem</a>:
</p>
<blockquote class="citation">
<p>
One more remark.
</p>
<p>
<code>is_lawrence_polytope</code> is very slow in cases, where the polytope does not have few vertices. Try checking this for <code>permutahedron(6)</code>.
</p>
</blockquote>
<p>
It is hard to have an algorithm that gets faster as the input gets larger!
</p>
</blockquote>
<p>
Sure. But its also nice to not recalculate something that is already known.
</p>
<blockquote class="citation">
<p>
In spite of that, yes, it might not be optimized, but I would not go into intricate implementation of the function unless there is yet a known use case.
</p>
</blockquote>
<p>
Whether a polytope is a Lawrence polytope can simply be decided from the incidence matrix.
It is simply the question, whether the vertices V can be labeled v<sub>1</sub>,...,v<sub>n</sub>,w<sub>1</sub>,...,w<sub>2m</sub> such that V\{v<sub>i</sub>} and V\{w<sub>2j</sub>,w<sub>2j+1</sub>} is a facet.
</p>
<p>
Moreover, the current version has issues. We discovered that <code>gale_transform()</code> is not normalized. At the moment the answer depends on the realization of the polytope. Also, the current code will return <code>True</code> for the bipyramid over a triangle. To my understanding this is not a Lawrence polytope as the Gale diagram is not symmetric with respect to multiplicity.
</p>
Ticketgh-kliemSat, 30 Mar 2019 15:30:28 GMT
https://trac.sagemath.org/ticket/27534#comment:9
https://trac.sagemath.org/ticket/27534#comment:9
<p>
Is a pyramid over a Lawrence polytope a Lawrence polytope? I think the definition should allow for an arbitrary number of points at the origin of the Gale diagram.
</p>
<p>
<code>polymake</code>'s construction of a Lawrence polytope of a polytope with a vertex at the origin will even have an odd number of points. This construction is according to Bernd Sturmfels' definition, I think.
</p>
<p>
Let V be the vertex matrix of a polytope. The Lawrence polytope will have the following vertices according to Günter Ziegler (Lectures on Polytopes):
</p>
<pre class="wiki"> \begin{pmatrix}
V & V \\
I_n & 2*I_n
\end{pmatrix},
</pre><p>
According to Bernd Sturmfels (<a class="ext-link" href="https://arxiv.org/pdf/math/0202104.pdf"><span class="icon"></span>https://arxiv.org/pdf/math/0202104.pdf</a>):
</p>
<pre class="wiki"> \begin{pmatrix}
V & 0 \\
I_n & I_n
\end{pmatrix},
</pre><p>
Both construction yield centrally symmetric Gale diagrams, but the second construction might not have an odd number of points, as pointed out.
</p>
<p>
Only the first construction will "add" for each point x in the Gale diagram a point -x.
</p>
<p>
Btw, the first construction will not have <code>gale_transform</code> be centrally symmetric, before normalizing. E.g. when applying it for the cube, those are the coordinates of the Gale transform:
</p>
<pre class="wiki">sage: P = polytopes.cube()
sage: I_n = matrix.identity(8)
sage: V = P.vertices_matrix()
sage: lambda_V = block_matrix([[V,V],[I_n, 2*I_n]])
sage: Polyhedron(lambda_V.transpose()).gale_transform()
[(2, 0, 0, 0),
(-1, 0, 0, 0),
(0, 2, 0, 0),
(0, -1, 0, 0),
(0, 0, 2, 0),
(0, 0, -1, 0),
(-2, -2, -2, 0),
(1, 1, 1, 0),
(0, 0, 0, 2),
(0, 0, 0, -1),
(-2, -2, 0, -2),
(1, 1, 0, 1),
(-2, 0, -2, -2),
(1, 0, 1, 1),
(4, 2, 2, 2),
(-2, -1, -1, -1)]
</pre>
TicketgitFri, 05 Apr 2019 08:13:50 GMTcommit changed
https://trac.sagemath.org/ticket/27534#comment:10
https://trac.sagemath.org/ticket/27534#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>a7849b3ecea4f36f7233940ee6d18a0af943013c</em> to <em>69cd2c3f76444244edc5fa2d9d38001ac695ba36</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=69cd2c3f76444244edc5fa2d9d38001ac695ba36"><span class="icon"></span>69cd2c3</a></td><td><code>improve is_lawrence and fix lawrence_polytope</code>
</td></tr></table>
TicketLaith RastanawiFri, 05 Apr 2019 08:30:20 GMTstatus changed
https://trac.sagemath.org/ticket/27534#comment:11
https://trac.sagemath.org/ticket/27534#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/27534#comment:5" title="Comment 5">gh-kliem</a>:
</p>
<blockquote class="citation">
<p>
One more remark.
</p>
<p>
<code>is_lawrence_polytope</code> is very slow in cases, where the polytope does not have few vertices. Try checking this for <code>permutahedron(6)</code>.
</p>
<p>
Instead of computing the Gale-transform, one could just grap the information from the facets.
</p>
<ol><li>Create a list of vertices <code>V</code>.
</li><li>Iterate through all facets <code>F</code> containing exactly <code>n-1</code> vertices.
</li><li>Remove the vertex not contained in <code>F</code> from <code>V</code> (this vertex "is" the origin in the Gale transform).
</li><li>Iterate through all facets <code>F</code> containing exactly <code>n-2</code> vertices.
</li><li>Let v_1,v_2 not be in <code>F</code>. If v_1 and v_2 in <code>V</code>, remove them.
</li></ol><p>
If at the end of this <code>V</code> is empty, the Gale diagram is centrally symmetric. If not, then it is not.
</p>
</blockquote>
<p>
This is really helpful and fast. I implemented this in <code>is_lawrence_polytope</code>.
</p>
<blockquote class="citation">
<p>
Both construction yield centrally symmetric Gale diagrams, but the second construction might not have an odd number of points, as pointed out.
</p>
</blockquote>
<p>
I decided to only put the construction given by Ziegler. It works in the case where the polytope is not full-dimensional.
</p>
TicketLaith RastanawiFri, 05 Apr 2019 08:34:48 GMT
https://trac.sagemath.org/ticket/27534#comment:12
https://trac.sagemath.org/ticket/27534#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/27534#comment:6" title="Comment 6">jipilab</a>:
</p>
<blockquote class="citation">
<p>
One suggestion:
</p>
<p>
Perles' example of a non-rational polytope uses lawrence extension to be constructed. It would be nice to add the example to the library of polytopes (either using lawrence extension or just hard-coding the vertices. Or even better, hard-coding the vertices and in the test of the function for the polytope, construct the polytope using lawrence extension and check that it is really combinatorially isomorphic.
</p>
</blockquote>
<p>
This would be a very nice example. I think this needs its own ticket "adding Perles's example to polytopes library". After that we can add it to the test of the function <code>lawrence_extension</code> .
</p>
TicketLaith RastanawiFri, 05 Apr 2019 08:37:40 GMTdescription, summary changed; keywords set
https://trac.sagemath.org/ticket/27534#comment:13
https://trac.sagemath.org/ticket/27534#comment:13
<ul>
<li><strong>keywords</strong>
<em>polytopes</em> <em>lawrence</em> <em>extension</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/27534?action=diff&version=13">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Lawrence Extension</em> to <em>Implement Lawrence extension for polytopes</em>
</li>
</ul>
TicketgitFri, 05 Apr 2019 12:13:47 GMTcommit changed
https://trac.sagemath.org/ticket/27534#comment:14
https://trac.sagemath.org/ticket/27534#comment:14
<ul>
<li><strong>commit</strong>
changed from <em>69cd2c3f76444244edc5fa2d9d38001ac695ba36</em> to <em>a975b55312cfd8227a88b934901005dbb6b7ef95</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=a975b55312cfd8227a88b934901005dbb6b7ef95"><span class="icon"></span>a975b55</a></td><td><code>change the name of the variable non_vertices to facet_non_vertices</code>
</td></tr></table>
TicketLaith RastanawiFri, 05 Apr 2019 12:16:41 GMT
https://trac.sagemath.org/ticket/27534#comment:15
https://trac.sagemath.org/ticket/27534#comment:15
<p>
Sorry. I know this is on "needs_review".
I only changed the name of a variable from <code>non_vertices</code> to <code>facet_non_vertices</code>.
</p>
Ticketgh-kliemFri, 05 Apr 2019 17:52:33 GMT
https://trac.sagemath.org/ticket/27534#comment:16
https://trac.sagemath.org/ticket/27534#comment:16
<pre class="wiki">+src/sage/geometry/polyhedron/base.py:509: undefined name 'x'
+src/sage/geometry/polyhedron/base.py:4030: 'sage.matrix.constructor.block_matrix' imported but unused
</pre><p>
Maybe one could add <code>x = None</code>, before line 503.
Then we don't get that <code>pyflakes</code> error anymore.
</p>
<p>
Delete line 4030.
</p>
Ticketgh-kliemFri, 05 Apr 2019 19:27:48 GMT
https://trac.sagemath.org/ticket/27534#comment:17
https://trac.sagemath.org/ticket/27534#comment:17
<p>
Tiny things:
</p>
<div class="wiki-code"><div class="code"><pre><span class="gd">- I_n= matrix.identity(n)
- lambda_V = block_matrix([[V, I_n],[V, 2*I_n]])
</span><span class="gi">+ I_n = matrix.identity(n)
+ lambda_V = block_matrix([[V, I_n], [V, 2*I_n]])
</span></pre></div></div><div class="wiki-code"><div class="code"><pre><span class="gi">+ For more information, see [BaSt1990]_.
</span><span class="gd">-
</span><span class="gi">+ """
</span><span class="gd">-
</span></pre></div></div><p>
I think, there are in general no blank lines after the end of the docstring <code>"""</code>.
</p>
<p>
Also there is a double blank line.
</p>
<pre class="wiki">sage: Q = polytopes.regular_polygon(4).pyramid()
</pre><p>
Instead of Q, I would maybe use something more descriptive as <code>egyptian</code> or <code>egyptian_py</code>.
Then one does not have to read all of <code>polytopes.regular_polygon(4).pyramid()</code> to understand the construction.
</p>
<p>
This is all that I can come up with.
</p>
TicketgitFri, 05 Apr 2019 21:29:55 GMTcommit changed
https://trac.sagemath.org/ticket/27534#comment:18
https://trac.sagemath.org/ticket/27534#comment:18
<ul>
<li><strong>commit</strong>
changed from <em>a975b55312cfd8227a88b934901005dbb6b7ef95</em> to <em>e5c6cad97afb517d6ccfee370f81869c6a492314</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=e5c6cad97afb517d6ccfee370f81869c6a492314"><span class="icon"></span>e5c6cad</a></td><td><code>fixing pyflakes undefined variable error/cleaning the code</code>
</td></tr></table>
TicketgitFri, 05 Apr 2019 21:31:54 GMTcommit changed
https://trac.sagemath.org/ticket/27534#comment:19
https://trac.sagemath.org/ticket/27534#comment:19
<ul>
<li><strong>commit</strong>
changed from <em>e5c6cad97afb517d6ccfee370f81869c6a492314</em> to <em>bc1b9cd71307b02eee6ff17e33aa3fe05089230e</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=bc1b9cd71307b02eee6ff17e33aa3fe05089230e"><span class="icon"></span>bc1b9cd</a></td><td><code>change variable name from egyption_py to egyption_pyramid</code>
</td></tr></table>
Ticketgh-kliemMon, 08 Apr 2019 08:35:59 GMTstatus changed
https://trac.sagemath.org/ticket/27534#comment:20
https://trac.sagemath.org/ticket/27534#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Looks fine to me.
</p>
TicketVolker BraunWed, 10 Apr 2019 15:28:40 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/27534#comment:21
https://trac.sagemath.org/ticket/27534#comment:21
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/27534</em> to <em>bc1b9cd71307b02eee6ff17e33aa3fe05089230e</em>
</li>
</ul>
TicketJean-Philippe LabbéTue, 16 Apr 2019 07:31:36 GMTcommit deleted
https://trac.sagemath.org/ticket/27534#comment:22
https://trac.sagemath.org/ticket/27534#comment:22
<ul>
<li><strong>commit</strong>
<em>bc1b9cd71307b02eee6ff17e33aa3fe05089230e</em> deleted
</li>
</ul>
<p>
Here is one things that could have been changed in this ticket:
</p>
<div class="wiki-code"><div class="code"><pre><span class="gd">- raise NotImplementedError("self must be a polytope")
</span><span class="gi">+ raise NotImplementedError("Only polytopes (compact polyhedra) are allowed.")
</span></pre></div></div><p>
like in <code>bounding_box</code> or
</p>
<div class="wiki-code"><div class="code"><pre><span class="gd">- raise NotImplementedError("self must be a polytope")
</span><span class="gi">+ raise NotImplementedError("The polytope has to be compact.")
</span></pre></div></div><p>
like in <code>barycentric_subdivision</code>. Usually <code>self</code> is replaced by something more informative about the actual object and making the requirement precise (in this case 'compactness'). Since polytope is not a universally defined word, mentioning compactness makes thing completely unambiguous.
</p>
<p>
This could be changed some other time when practical.
</p>
Ticket