Sage: Ticket #18190: bindings to Latte
https://trac.sagemath.org/ticket/18190
<p>
Sage lacks a lot of feature that are in Latte:
</p>
<ul><li>fast integer point counting in polyhedron
</li><li>computation of Ehrart polynomial
</li></ul><p>
just to mention some of them.
</p>
<p>
Note that Latte has no documentation for its library (only the various command line does have). So it might be nice to ask whether it is stable accross versions to upstream.
</p>
<p>
See also:
</p>
<ul><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/18211" title="#18211: enhancement: Computing Ehrhart polynomials with LattE (closed: fixed)">#18211</a>: Computing Ehrhart polynomials with LattE (command line interface)
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18190
Trac 1.2Dima PasechnikTue, 14 Apr 2015 14:53:00 GMTdescription changed
https://trac.sagemath.org/ticket/18190#comment:1
https://trac.sagemath.org/ticket/18190#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18190?action=diff&version=1">diff</a>)
</li>
</ul>
TicketVincent DelecroixTue, 14 Apr 2015 20:54:35 GMTdependencies set
https://trac.sagemath.org/ticket/18190#comment:2
https://trac.sagemath.org/ticket/18190#comment:2
<ul>
<li><strong>dependencies</strong>
set to <em>#18190</em>
</li>
</ul>
TicketVincent DelecroixTue, 14 Apr 2015 20:54:47 GMTdependencies changed
https://trac.sagemath.org/ticket/18190#comment:3
https://trac.sagemath.org/ticket/18190#comment:3
<ul>
<li><strong>dependencies</strong>
changed from <em>#18190</em> to <em>#18195</em>
</li>
</ul>
TicketJeroen DemeyerTue, 14 Apr 2015 21:09:45 GMT
https://trac.sagemath.org/ticket/18190#comment:4
https://trac.sagemath.org/ticket/18190#comment:4
<p>
What is the input for <code>latte</code>? I assume a polyhedron given by its <em>vertices</em> (V-representation) or does it also support a polyhedron given by constraints (H-representation)?
</p>
TicketVincent DelecroixTue, 14 Apr 2015 21:14:18 GMT
https://trac.sagemath.org/ticket/18190#comment:5
https://trac.sagemath.org/ticket/18190#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18190#comment:4" title="Comment 4">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
What is the input for <code>latte</code>? I assume a polyhedron given by its <em>vertices</em> (V-representation) or does it also support a polyhedron given by constraints (H-representation)?
</p>
</blockquote>
<p>
By constraints. Actually it would be quite straightforward to have an implementation creating a temporary file and just call <code>count</code> on this file. The input is basically the same as <code>cdd</code> as defined in <code>sage.geometry.polyhedron.cdd_file_format</code>.
</p>
<p>
But the aim of the ticket is to implement a more direct interface (Matthias Koeppe developing latte is in the loop). Though there is also some work needed from latte side.
</p>
<p>
Vincent
</p>
TicketJeroen DemeyerTue, 14 Apr 2015 21:20:26 GMT
https://trac.sagemath.org/ticket/18190#comment:6
https://trac.sagemath.org/ticket/18190#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18190#comment:5" title="Comment 5">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18190#comment:4" title="Comment 4">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
What is the input for <code>latte</code>? I assume a polyhedron given by its <em>vertices</em> (V-representation) or does it also support a polyhedron given by constraints (H-representation)?
</p>
</blockquote>
<p>
By constraints.
</p>
</blockquote>
<p>
...only?
</p>
<p>
It is required that the vertices are lattice points?
</p>
<p>
I ask because <code>Polyhedron()</code> in Sage always computes the vertices. I know from <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/17920" title="#17920: enhancement: Reimplement IntegerLists using Polyhedron.integral_points() (needs_work)">#17920</a> that this step sometimes takes more time than enumerating the points. So if you really want efficiency, you would want a way to define a <code>Polyhedron</code> <em>without</em> computing its vertices.
</p>
TicketDima PasechnikTue, 14 Apr 2015 21:28:07 GMT
https://trac.sagemath.org/ticket/18190#comment:7
https://trac.sagemath.org/ticket/18190#comment:7
<p>
LMGIFY: <a class="ext-link" href="https://www.math.ucdavis.edu/~latte/software/packages/latte_current/manual_v1.7.2.pdf"><span class="icon"></span>https://www.math.ucdavis.edu/~latte/software/packages/latte_current/manual_v1.7.2.pdf</a>
</p>
TicketVolker BraunTue, 14 Apr 2015 23:00:33 GMT
https://trac.sagemath.org/ticket/18190#comment:8
https://trac.sagemath.org/ticket/18190#comment:8
<p>
Barvinok's method always reduces to counting points in lattice simplices afaik. So you either triangulate (=more than just knowing vertices) or write it as formal addition & subtraction of simplices (less simplices but more complicated to do)
</p>
TicketMatthias KöppeTue, 14 Apr 2015 23:25:48 GMT
https://trac.sagemath.org/ticket/18190#comment:9
https://trac.sagemath.org/ticket/18190#comment:9
<p>
LattE's input is either the vertices (V-rep) or the inequalities (H-rep).
It computes the other representation of the polyhedron (and makes other polyhedral computations) by calling either cddlib, or 4ti2.
(Ideally, there should be a way to feed both representations into LattE to avoid recomputation, but this is not implemented.)
</p>
<p>
@jdemeyer: The vertices can be rational.
</p>
TicketMatthias KöppeWed, 15 Apr 2015 00:22:17 GMT
https://trac.sagemath.org/ticket/18190#comment:10
https://trac.sagemath.org/ticket/18190#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18190#comment:5" title="Comment 5">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Actually it would be quite straightforward to have an implementation creating a temporary file and just call <code>count</code> on this file. The input is basically the same as <code>cdd</code> as defined in <code>sage.geometry.polyhedron.cdd_file_format</code>.
</p>
</blockquote>
<p>
In fact, when "count" is invoked with --cdd, then CDD file format is accepted.
</p>
<p>
So building a preliminary interface should indeed be very easy.
</p>
TicketVincent DelecroixWed, 15 Apr 2015 19:55:54 GMTdescription changed
https://trac.sagemath.org/ticket/18190#comment:11
https://trac.sagemath.org/ticket/18190#comment:11
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18190?action=diff&version=11">diff</a>)
</li>
</ul>
TicketMatthias KöppeThu, 16 Apr 2015 16:00:13 GMTcc changed
https://trac.sagemath.org/ticket/18190#comment:12
https://trac.sagemath.org/ticket/18190#comment:12
<ul>
<li><strong>cc</strong>
<em>Brandon Dutra</em> added
</li>
</ul>
TicketJeroen DemeyerTue, 23 Jun 2015 13:49:26 GMTcomponent changed
https://trac.sagemath.org/ticket/18190#comment:13
https://trac.sagemath.org/ticket/18190#comment:13
<ul>
<li><strong>component</strong>
changed from <em>interfaces</em> to <em>interfaces: optional</em>
</li>
</ul>
Ticket