A primal Barvinok algorithm based on irrational decompositions
arXiv:math/0603308 · doi:10.1137/060664768
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.
arXiv commentv3: New all-primal algorithm. v4: Extended introduction, updated computational results. To appear in SIAM Journal on Discrete Mathematics
References in corpus (2)
Cited by in corpus (16)
- Nonlinear Integer Programming
- Counting with rational generating functions
- 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
- Theorems of Brion, Lawrence, and Varchenko on rational generating functions for cones
- 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
- Decomposition Methods for Nonlinear Optimization and Data Mining
- The combinatorics of interval-vector polytopes