Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra

DOI10.1007/S10208-011-9106-4zbMATH Open1255.05006arXiv1011.1602OpenAlexW2098122576MaRDI QIDQ695630FDOQ695630

Authors: Jesús A. De Loera, Velleda Baldoni, Nicole Berline, Matthias Köppe, Michèle Vergne 

Publication date: 21 December 2012

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function h. Our technique is based on a refinement of an algorithm of A. Barvinok [Computing the Ehrhart quasi-polynomial of a rational simplex, Math. Comp. 75 (2006), pp. 1449--1466] in the unweighted case (i.e., h = 1). In contrast to Barvinok's method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach we report on computational experiments which show even our simple implementation can compete with state of the art software.

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

Recommendations

• Computing the Ehrhart quasi-polynomial of a rational simplex
• Counting with rational generating functions
• Effective lattice point counting in rational convex polytopes
• Computing the Ehrhart polynomial of a convex lattice polytope
• Three Ehrhart quasi-polynomials

zbMATH Keywords

polynomial-time algorithmsBarvinok's methodcounting lattice points inside convex polytopesEhrhart functionsexponential sums and integralshighest degree coefficientsintermediate sumsrational simple polytopeweighted Ehrhart quasi-polynomial

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Exact enumeration problems, generating functions (05A15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Cites Work

• Effective lattice point counting in rational convex polytopes
• Computing the Continuous Discretely
• Title not available (Why is that?)
• Triangulations. Structures for algorithms and applications
• Primal-dual methods for vertex and facet enumeration
• The many aspects of counting lattice points in polytopes
• Residue formulae, vector partition functions and lattice points in rational polytopes
• Points entiers dans les polyèdres convexes
• How to integrate a polynomial over a simplex
• Title not available (Why is that?)
• Lattice points in simple polytopes
• Title not available (Why is that?)
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• Integer Polynomial Optimization in Fixed Dimension
• Integer points in polyhedra
• A Primal Barvinok Algorithm Based on Irrational Decompositions
• Counting with rational generating functions
• Pick's theorem and the Todd class of a toric variety
• Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
• Computing the Ehrhart polynomial of a convex lattice polytope
• Computing the Ehrhart quasi-polynomial of a rational simplex
• Intermediate sums on polyhedra: computation and real Ehrhart theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lattice points, Dedekind sums, and Ehrhart polynomials of lattice polyhedra
• Title not available (Why is that?)
• Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of a rational polytope

Cited In (21)

• Exploiting symmetries in polyhedral computations
• Computations of volumes and Ehrhart series in four candidates elections
• Computing the Ehrhart quasi-polynomial of a rational simplex
• Exploiting polyhedral symmetries in social choice
• On the number of integer points in translated and expanded polyhedra
• Three Ehrhart quasi-polynomials
• Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of a rational polytope
• On the score sheets of a round-robin football tournament
• Enumerating projections of integer points in unbounded polyhedra
• Intermediate sums on polyhedra: computation and real Ehrhart theory
• Tropical Ehrhart theory and tropical volume
• The many aspects of counting lattice points in polytopes
• Counting with rational generating functions
• Counting chemical compositions using Ehrhart quasi-polynomials
• The computation of generalized Ehrhart series in normaliz
• Dilated floor functions having nonnegative commutator. I: Positive and mixed sign dilations
• Strange expectations and simultaneous cores
• Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
• Notes on K-Semistability of Toric Polarized Varieties
• Computing Galois groups of Ehrhart polynomials in OSCAR
• On the polynomiality of orbifold Gromov-Witten theory of root stacks

Uses Software

• Maple
• LattE

This page was built for publication: Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q695630)