Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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