Details:
Title  Effective lattice point counting in rational convex polytopes  Author(s)  Jesús A., Raymond Hemmecke, Jeremiah Tauzer, R. Yoshida  Type  Article in Journal  Abstract  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 branchandbound 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 facetdefining inequalities is much smaller compared to the number of vertices.  Keywords  Barvinok’s algorithm, Convex rational polyhedra, Ehrhart quasipolynomials, Enumeration of lattice points, Generating functions, Lattice points, Rational functions  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717104000422 
Language  English  Journal  Journal of Symbolic Computation  Volume  38  Number  4  Pages  1273  1302  Year  2004  Note  Symbolic Computation in Algebra and Geometry  Edition  0  Translation 
No  Refereed 
No 
