Effective Lattice Point Counting
in Rational Convex Polytopes
Jesús A. De Loera, Raymond Hemmecke
Jeremiah Tauzer, and Ruriko Yoshida
Abstract:
This online 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.
We report on computational experiments with multiway contingency
tables, knapsack type problems, rational polygons, and flow
polytopes. We prove that our this kind 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 ``polar'' 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.
The complete paper is available to view as a pdf
 Effective Lattice Point Counting in Rational Convex Polytopes
Additional papers and websites are also available to view
Counting Integer Flows in Networks
Total Residues for Counting Lattice Points in Unimodular Polytopes
Polyhedral Cones of Magic Cubes and Squares
If you do not have Adobe Reader, you can download it here.
|
