bindings to Latte

[videlec]

Sage lacks a lot of feature that are in Latte:

• fast integer point counting in polyhedron
• computation of Ehrart polynomial just to mention some of them.

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.

See also:

• 18211: Computing Ehrhart polynomials with LattE (command line interface)

Depends on #18195

CC: @dimpase @novoselt @vbraun @nthiery @tscrim @haraldschilly @fchapoton @nathanncohen @sagetrac-bedutra

Component: interfaces: optional

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

[dimpase]

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
 Sage lacks a lot of feature that are in Latte:
-- integer point counting in polyhedron
+- fast integer point counting in polyhedron
 - computation of Ehrart polynomial
 just to mention some of them.

[videlec]

Dependencies: #18190

[videlec]

Changed dependencies from #18190 to #18195

[jdemeyer]

comment:4

What is the input for latte? I assume a polyhedron given by its vertices (V-representation) or does it also support a polyhedron given by constraints (H-representation)?

[videlec]

comment:5

Replying to @jdemeyer:

What is the input for latte? I assume a polyhedron given by its vertices (V-representation) or does it also support a polyhedron given by constraints (H-representation)?

By constraints. Actually it would be quite straightforward to have an implementation creating a temporary file and just call count on this file. The input is basically the same as cdd as defined in sage.geometry.polyhedron.cdd_file_format.

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.

Vincent

[jdemeyer]

comment:6

Replying to @videlec:

Replying to @jdemeyer:

What is the input for latte? I assume a polyhedron given by its vertices (V-representation) or does it also support a polyhedron given by constraints (H-representation)?

By constraints.

...only?

It is required that the vertices are lattice points?

I ask because Polyhedron() in Sage always computes the vertices. I know from #17920 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 Polyhedron without computing its vertices.

[dimpase]

comment:7

LMGIFY: https://www.math.ucdavis.edu/~latte/software/packages/latte_current/manual_v1.7.2.pdf

[vbraun]

comment:8

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)

[mkoeppe]

comment:9

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

@jdemeyer: The vertices can be rational.

[mkoeppe]

comment:10

Replying to @videlec:

Actually it would be quite straightforward to have an implementation creating a temporary file and just call count on this file. The input is basically the same as cdd as defined in sage.geometry.polyhedron.cdd_file_format.

In fact, when "count" is invoked with --cdd, then CDD file format is accepted.

So building a preliminary interface should indeed be very easy.

[videlec]

Description changed:

--- 
+++ 
@@ -4,3 +4,6 @@
 just to mention some of them.

 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.
+
+See also:
+- #18211: Computing Ehrhart polynomials with LattE (command line interface)