Computing parametric rational generating functions with a primal Barvinok algorithm
From MaRDI portal
Symbolic computation and algebraic computation (68W30) Computational aspects related to convexity (52B55) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Combinatorial complexity of geometric structures (52C45) Dissections and valuations (Hilbert's third problem, etc.) (52B45)
Abstract: Computations with Barvinok's short rational generating functions are traditionally being performed in the dual space, to avoid the combinatorial complexity of inclusion--exclusion formulas for the intersecting proper faces of cones. We prove that, on the level of indicator functions of polyhedra, there is no need for using inclusion--exclusion formulas to account for boundary effects: All linear identities in the space of indicator functions can be purely expressed using half-open variants of the full-dimensional polyhedra in the identity. This gives rise to a practically efficient, parametric Barvinok algorithm in the primal space.
Recommendations
- Computing with an algebraic-perturbation variant of Barvinok's algorithm
- Counting with rational generating functions
- The complexity of generating functions for integer points in polyhedra and beyond
- An algebraic-perturbation variant of Barvinok's algorithm
- Short rational generating functions for lattice point problems
Cited in
(23)- Enumeration and unimodular equivalence of empty delta-modular simplices
- A Primal Barvinok Algorithm Based on Irrational Decompositions
- Ehrhart tensor polynomials
- The Martin Gardner Polytopes
- The complexity of generating functions for integer points in polyhedra and beyond
- On the relationship between Ehrhart unimodality and Ehrhart positivity
- Three Ehrhart quasi-polynomials
- Lipschitz polytopes of posets and permutation statistics
- Enumerating projections of integer points in unbounded polyhedra
- Computing convex hulls and counting integer points with \texttt{polymake}
- An algebraic-perturbation variant of Barvinok's algorithm
- On lattice point counting in \(\varDelta\)-modular polyhedra
- Arithmetic aspects of symmetric edge polytopes
- Combinatorial mixed valuations
- Counting integer points in parametric polytopes using Barvinok's rational functions
- The computation of generalized Ehrhart series in normaliz
- \(h^\ast \)-polynomials of zonotopes
- The power of pyramid decomposition in Normaliz
- Weighted Ehrhart theory: extending Stanley's nonnegativity theorem
- Polyhedral omega: a new algorithm for solving linear Diophantine systems
- Ehrhart polynomials of matroid polytopes and polymatroids
- Computing with an algebraic-perturbation variant of Barvinok's algorithm
- \(h^*\) -vectors of graph polytopes using activities of dissecting spanning trees
This page was built for publication: Computing parametric rational generating functions with a primal Barvinok algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010722)
