A primal Barvinok algorithm based on irrational decompositions

Abstract

We introduce variants of Barvinok's algorithm for counting lattice points in polyhedra. The new algorithms are based on irrational signed decomposition in the primal space and the construction of rational generating functions for cones with low index. We give computational results that show that the new algorithms are faster than the existing algorithms by a large factor.

v3: New all-primal algorithm. v4: Extended introduction, updated computational results. To appear in SIAM Journal on Discrete Mathematics

Cited by in corpus (14)

• Nonlinear Integer Programming
• Ehrhart polynomials of matroid polytopes and polymatroids
• A Euclid style algorithm for MacMahon's partition analysis
• Intermediate Sums on Polyhedra: Computation and Real Ehrhart Theory
• Positivity theorems for solid-angle polynomials
• Minkowski length of 3D lattice polytopes
• Computing parametric rational generating functions with a primal Barvinok algorithm
• Complexity of short Presburger arithmetic
• Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
• Enumerating projections of integer points in unbounded polyhedra
• Summing a polynomial function over integral points of a polygon. User's guide
• Matroid Polytopes: Algorithms, Theory, and Applications
• The combinatorics of interval-vector polytopes
• Decomposition Methods for Nonlinear Optimization and Data Mining