Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleEffective lattice point counting in rational convex polytopes
Author(s) Jesús A., Raymond Hemmecke, Jeremiah Tauzer, R. Yoshida
TypeArticle in Journal
AbstractThis 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.
KeywordsBarvinok’s algorithm, Convex rational polyhedra, Ehrhart quasi-polynomials, Enumeration of lattice points, Generating functions, Lattice points, Rational functions
URL http://www.sciencedirect.com/science/article/pii/S0747717104000422
JournalJournal of Symbolic Computation
Pages1273 - 1302
NoteSymbolic Computation in Algebra and Geometry
Translation No
Refereed No