Sage: Ticket #21041: Polyhedron.integral_points(): Generalize Smith form based enumeration to rational and semi-rational polytopes
https://trac.sagemath.org/ticket/21041
<p>
As a follow-up to <a class="closed ticket" href="https://trac.sagemath.org/ticket/21037" title="#21037: defect: Polyhedron.integral_points() fails for non-rational polytopes (closed: fixed)">#21037</a>, the method for integer point enumeration using triangulation and Smith form (a simple implementation of normaliz's method (see <a class="closed ticket" href="https://trac.sagemath.org/ticket/20885" title="#20885: enhancement: Normaliz/PyNormaliz interface: Fast backend for polyhedra, ... (closed: fixed)">#20885</a> <a class="ticket" href="https://trac.sagemath.org/ticket/21041#comment:6" title="Comment 6">comment:6</a>) in <code>simplex_points</code> is limited to lattice polytopes. Normaliz is much faster and has an implementation for rational (non-lattice) polytopes. A generalization to include the case of semi-rational polytopes (i.e., possibly irrational translations of lattice polytopes) could be valuable; example:
</p>
<pre class="wiki"> sage: P = Polyhedron(vertices=((0, 0), (1743,3134))) + 1/1000*vector(AA, [AA(sqrt(5)), AA(sqrt(5))])
sage: P.integral_points() # takes LONG
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/21041
Trac 1.2Travis ScrimshawSun, 17 Jul 2016 23:46:26 GMT
https://trac.sagemath.org/ticket/21041#comment:1
https://trac.sagemath.org/ticket/21041#comment:1
<p>
Would it be beneficial to expand a rational polytope so that its points are integral, and then filter out the points which would not be integers upon shrinking?
</p>
<p>
I'm guessing the way to check for translates of a rational/lattice polytope is to actually look at the differences of the vertices relative to a fixed vertex?
</p>
TicketMatthias KöppeMon, 18 Jul 2016 11:07:43 GMT
https://trac.sagemath.org/ticket/21041#comment:2
https://trac.sagemath.org/ticket/21041#comment:2
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21041#comment:1" title="Comment 1">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Would it be beneficial to expand a rational polytope so that its points are integral, and then filter out the points which would not be integers upon shrinking?
</p>
</blockquote>
<p>
Yes, that could be a simple technique that would require only small changes of the code.
The normaliz manual (<a class="ext-link" href="https://www.normaliz.uni-osnabrueck.de/wp-content/uploads/2016/04/Normaliz3.1.1Documentation.pdf"><span class="icon"></span>https://www.normaliz.uni-osnabrueck.de/wp-content/uploads/2016/04/Normaliz3.1.1Documentation.pdf</a>, page 64, section 6.1) explains an "approximation technique" similar to this idea.
</p>
<blockquote class="citation">
<p>
I'm guessing the way to check for translates of a rational/lattice polytope is to actually look at the differences of the vertices relative to a fixed vertex?
</p>
</blockquote>
<p>
It is explained, for example, in <a class="ext-link" href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r16/pdf"><span class="icon"></span>http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r16/pdf</a> Lemma 11.
</p>
TicketTravis ScrimshawMon, 18 Jul 2016 14:33:51 GMT
https://trac.sagemath.org/ticket/21041#comment:3
https://trac.sagemath.org/ticket/21041#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21041#comment:2" title="Comment 2">mkoeppe</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21041#comment:1" title="Comment 1">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Would it be beneficial to expand a rational polytope so that its points are integral, and then filter out the points which would not be integers upon shrinking?
</p>
</blockquote>
<p>
Yes, that could be a simple technique that would require only small changes of the code.
The normaliz manual (<a class="ext-link" href="https://www.normaliz.uni-osnabrueck.de/wp-content/uploads/2016/04/Normaliz3.1.1Documentation.pdf"><span class="icon"></span>https://www.normaliz.uni-osnabrueck.de/wp-content/uploads/2016/04/Normaliz3.1.1Documentation.pdf</a>, page 64, section 6.1) explains an "approximation technique" similar to this idea.
</p>
</blockquote>
<p>
The hard part, to me, of this would be constructing the approximation lattice polytope. Would we just take the convex hull of all of the cell containing each of the non-integral vertices of the original polytope? Or is there a smarter method?
</p>
<p>
I'm thinking we should implement both approaches (at least for now to see if one definitely beats the other). Plus, the approximation could be used as a general purpose technique.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
I'm guessing the way to check for translates of a rational/lattice polytope is to actually look at the differences of the vertices relative to a fixed vertex?
</p>
</blockquote>
<p>
It is explained, for example, in <a class="ext-link" href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r16/pdf"><span class="icon"></span>http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r16/pdf</a> Lemma 11.
</p>
</blockquote>
<p>
Thank you for the reference. Do you think you could provide this implementation? I am pretty sure I could do the first half above.
</p>
TicketMatthias KöppeMon, 18 Jul 2016 14:42:23 GMT
https://trac.sagemath.org/ticket/21041#comment:4
https://trac.sagemath.org/ticket/21041#comment:4
<p>
This should have low priority until someone "really" wants to do computations with semirational polytopes.
For the more common case of rational polytopes, with MUCH less effort one can make an "easy" implementation of a normaliz interface (using file passing instead of using libnormaliz).
</p>
TicketAndrey NovoseltsevMon, 18 Jul 2016 14:54:51 GMT
https://trac.sagemath.org/ticket/21041#comment:5
https://trac.sagemath.org/ticket/21041#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21041#comment:4" title="Comment 4">mkoeppe</a>:
</p>
<blockquote class="citation">
<p>
For the more common case of rational polytopes, with MUCH less effort one can make an "easy" implementation of a normaliz interface (using file passing instead of using libnormaliz).
</p>
</blockquote>
<p>
Note that such file passings and system calls add a considerable constant overhead (perhaps 0.1s on modern systems). This makes it horrible for large numbers of small polytopes. So it would be nice to have a library interface even though I don't volunteer to implement it ;-)
</p>
TicketTravis ScrimshawMon, 18 Jul 2016 14:55:43 GMT
https://trac.sagemath.org/ticket/21041#comment:6
https://trac.sagemath.org/ticket/21041#comment:6
<p>
Perhaps we should split this into 2 tickets, one for the rational case(s) and one of the semirational case? I can probably get the rational case(s) done tonight.
</p>
<p>
Unfortunately I cannot write code to interface with (lib)normaliz (addendum - without taking some time to do some reading and experimenting), but I will be happy to review it.
</p>
TicketMatthias KöppeMon, 18 Jul 2016 15:00:01 GMT
https://trac.sagemath.org/ticket/21041#comment:7
https://trac.sagemath.org/ticket/21041#comment:7
<p>
I'm visiting the normaliz people later this week. Maybe we will make a quick libnormaliz interface. Stay tuned.
</p>
TicketMatthias KöppeSun, 27 Nov 2016 02:20:55 GMTcc changed
https://trac.sagemath.org/ticket/21041#comment:8
https://trac.sagemath.org/ticket/21041#comment:8
<ul>
<li><strong>cc</strong>
<em>Winfried Bruns</em> added
</li>
</ul>
<p>
For the rational case, we now have an implementation using normaliz in <a class="closed ticket" href="https://trac.sagemath.org/ticket/20885" title="#20885: enhancement: Normaliz/PyNormaliz interface: Fast backend for polyhedra, ... (closed: fixed)">#20885</a>. It can handle for example this:
</p>
<pre class="wiki">sage: P = Polyhedron(vertices=((0, 0), (1789345,37121))) + 1/1000*polytopes.hypercube(2)
sage: V=P.vertices_list()
sage: P = Polyhedron(vertices=V, backend='normaliz')
sage: %timeit P.integral_points()
1 loop, best of 3: 134 ms per loop
sage: len(P.integral_points())
3654
</pre>
TicketMatthias KöppeTue, 29 Nov 2016 23:50:57 GMTsummary changed
https://trac.sagemath.org/ticket/21041#comment:9
https://trac.sagemath.org/ticket/21041#comment:9
<ul>
<li><strong>summary</strong>
changed from <em>Polyhedron.integral_points(): Generalize Smith form based enumeration to semi-rational polytopes</em> to <em>Polyhedron.integral_points(): Generalize Smith form based enumeration to rational and semi-rational polytopes</em>
</li>
</ul>
Ticket