Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
From MaRDI portal
(Redirected from Publication:695630)
polynomial-time algorithmsBarvinok's methodcounting lattice points inside convex polytopesEhrhart functionsexponential sums and integralshighest degree coefficientsintermediate sumsrational simple polytopeweighted Ehrhart quasi-polynomial
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4216777 (Why is no real title available?)
- scientific article; zbMATH DE number 95277 (Why is no real title available?)
- scientific article; zbMATH DE number 2120513 (Why is no real title available?)
- scientific article; zbMATH DE number 795108 (Why is no real title available?)
- scientific article; zbMATH DE number 1405493 (Why is no real title available?)
- scientific article; zbMATH DE number 2223034 (Why is no real title available?)
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- A Primal Barvinok Algorithm Based on Irrational Decompositions
- Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
- Computing the Continuous Discretely
- Computing the Ehrhart polynomial of a convex lattice polytope
- Computing the Ehrhart quasi-polynomial of a rational simplex
- Counting with rational generating functions
- Effective lattice point counting in rational convex polytopes
- How to integrate a polynomial over a simplex
- Integer Polynomial Optimization in Fixed Dimension
- Integer points in polyhedra
- Intermediate sums on polyhedra: computation and real Ehrhart theory
- Lattice points in simple polytopes
- Lattice points, Dedekind sums, and Ehrhart polynomials of lattice polyhedra
- Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of a rational polytope
- Pick's theorem and the Todd class of a toric variety
- Points entiers dans les polyèdres convexes
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Primal-dual methods for vertex and facet enumeration
- Residue formulae, vector partition functions and lattice points in rational polytopes
- The many aspects of counting lattice points in polytopes
- Triangulations. Structures for algorithms and applications
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
- The computation of generalized Ehrhart series in normaliz
- Counting chemical compositions using Ehrhart quasi-polynomials
- Strange expectations and simultaneous cores
- Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
- Dilated floor functions having nonnegative commutator. I: Positive and mixed sign dilations
- Notes on K-Semistability of Toric Polarized Varieties
- On the polynomiality of orbifold Gromov-Witten theory of root stacks
- Computing Galois groups of Ehrhart polynomials in OSCAR
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)
