Computing parametric rational generating functions with a primal Barvinok algorithm

zbMATH Open1180.52014arXiv0705.3651MaRDI QIDQ1010722FDOQ1010722

Authors: Matthias Köppe, Sven Verdoolaege 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0705.3651

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

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

Mathematics Subject Classification ID

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)

Cited In (23)

• 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
• Weighted Ehrhart theory: extending Stanley's nonnegativity theorem
• The power of pyramid decomposition in Normaliz
• 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
• Enumeration and unimodular equivalence of empty delta-modular simplices

Uses Software

• LattE
• TOPCOM

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)