Computing parametric rational generating functions with a primal Barvinok algorithm

MaRDI QIDQ1010722zbMATH OpenFDO

Authors Matthias Köppe, Sven Verdoolaege

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/0705.3651, https://eudml.org/doc/117215, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r16.html

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

Mathematics Subject Classification ID

Dissections and valuations (Hilbert's third problem, etc.) (52B45) Computational aspects related to convexity (52B55) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Combinatorial complexity of geometric structures (52C45) Symbolic computation and algebraic computation (68W30)

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.

Review text

Summary: 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 partially 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

(24)

• Ehrhart polynomials of matroid polytopes and polymatroids
• Ehrhart tensor polynomials
• Computing with an algebraic-perturbation variant of Barvinok's algorithm
• On the relationship between Ehrhart unimodality and Ehrhart positivity
• On lattice point counting in -modular polyhedra
• Polyhedral omega: a new algorithm for solving linear Diophantine systems
• Computing convex hulls and counting integer points with \texttt{polymake}
• Combinatorial mixed valuations
• Three Ehrhart quasi-polynomials
• An algebraic-perturbation variant of Barvinok's algorithm
• The Martin Gardner Polytopes
• Enumerating projections of integer points in unbounded polyhedra
• \(h^\ast \)-polynomials of zonotopes
• The computation of generalized Ehrhart series in normaliz
• Arithmetic aspects of symmetric edge polytopes
• A Primal Barvinok Algorithm Based on Irrational Decompositions
• The complexity of generating functions for integer points in polyhedra and beyond
• h^* -vectors of graph polytopes using activities of dissecting spanning trees
• Enumeration and unimodular equivalence of empty delta-modular simplices
• Weighted Ehrhart theory: extending Stanley's nonnegativity theorem
• A new and faster representation for counting integer points in parametric polyhedra
• Lipschitz polytopes of posets and permutation statistics
• The power of pyramid decomposition in Normaliz
• Counting integer points in parametric polytopes using Barvinok's rational functions

Describes a project that uses

Uses Software

• TOPCOM
• LattE

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)