Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

New variants of Barvinok's algorithm for computing the Ehrhart series of rational polytopes

Algebra & Discrete Mathematics

Speaker: Matthias Koeppe, Otto-von-Guericke-Universität Magdeburg
Location: 1147 MSB
Start time: Fri, Jun 1 2007, 3:10PM

We introduce variants of Barvinok's algorithm for counting lattice points in polyhedra. The traditional implementations of Barvinok's algorithm (as in the LattE code by De Loera et al.) perform signed decompositions in the dual space, i.e., they compute with the polars of rational cones. The new algorithms are based on signed decompositions in the primal space. To remove the combinatorial complexity of inclusion-exclusion formulas in the primal space, we use two new techniques called "irrational" decomposition and "parametric exact" decomposition. Another new technique is the construction of rational generating functions for simplicial cones with low index. We give computational results with our new version of LattE ("macchiato") that show that the new algorithms are faster than the existing algorithms by orders of magnitude. The talk is based on my recent papers arXiv:math/0603308 [math.CO] and arXiv:0705.3651 [math.CO].