Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
New variants of Barvinok's algorithm for computing the Ehrhart series of rational polytopesAlgebra & 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
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