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 |
Description
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].