Effective lattice point counting in rational convex polytopes

This paper discusses algorithms and software for the enumeration of all lattice points inside a rational convex polytope: we describe LattE, a computer package for lattice point enumeration which contains the first implementation of A. Barvinok’s algorithm (Math. Oper. Res. 19 (1994) 769). We report...

Full description

Saved in:
Bibliographic Details
Published in:Journal of symbolic computation 2004-10, Vol.38 (4), p.1273-1302
Main Authors: De Loera, Jesús A., Hemmecke, Raymond, Tauzer, Jeremiah, Yoshida, Ruriko
Format: Article
Language:English
Subjects:
Barvinok’s algorithm
Convex rational polyhedra
Ehrhart quasi-polynomials
Enumeration of lattice points
Generating functions
Lattice points
Rational functions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper discusses algorithms and software for the enumeration of all lattice points inside a rational convex polytope: we describe LattE, a computer package for lattice point enumeration which contains the first implementation of A. Barvinok’s algorithm (Math. Oper. Res. 19 (1994) 769). We report on computational experiments with multiway contingency tables, knapsack type problems, rational polygons, and flow polytopes. We prove that these kinds of symbolic–algebraic ideas surpass the traditional branch-and-bound enumeration and in some instances LattE is the only software capable of counting. Using LattE, we have also computed new formulas of Ehrhart (quasi-)polynomials for interesting families of polytopes (hypersimplices, truncated cubes, etc). We end with a survey of other “algebraic–analytic” algorithms, including a “homogeneous” variation of Barvinok’s algorithm which is very fast when the number of facet-defining inequalities is much smaller compared to the number of vertices.
ISSN:0747-7171
1095-855X
DOI:10.1016/j.jsc.2003.04.003