Effective lattice point counting in rational convex polytopes

DOI10.1016/J.JSC.2003.04.003zbMath1137.52303OpenAlexW2033084216MaRDI QIDQ2643564

Raymond Hemmecke, Jeremiah Tauzer, Ruriko Yoshida, Jesús A. De Loera

Publication date: 24 August 2007

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2003.04.003

zbMATH Keywords

generating functions rational functions lattice points Barvinok's algorithm Ehrhart quasi-polynomials convex rational polyhedra enumeration of lattice points

Mathematics Subject Classification ID

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

Related Items (73)

Petri Net Reductions for Counting Markings ⋮ Polyhedral omega: a new algorithm for solving linear Diophantine systems ⋮ On the pseudo-periodicity of the integer hull of parametric convex polygons ⋮ Quantifying software reliability via model-counting ⋮ Column basis reduction and decomposable knapsack problems ⋮ Polynomial Time Reachability Analysis in Discrete State Chemical Reaction Networks Obeying Conservation Laws ⋮ Computing points of bounded height in projective space over a number field ⋮ Analyzing the Practical Relevance of the Condorcet Loser Paradox and the Agenda Contraction Paradox ⋮ Exploring the No-Show Paradox for Condorcet Extensions ⋮ IAC Probability Calculations in Voting Theory: Progress Report ⋮ On Dedekind's problem for complete simple games ⋮ A chaotic lattice field theory in one dimension* ⋮ Estimating the volume of the solution space of SMT(LIA) constraints by a flat histogram method ⋮ Short rational functions for toric algebra and applications ⋮ On lattice point counting in \(\varDelta\)-modular polyhedra ⋮ How to find the convex hull of all integer points in a polyhedron? ⋮ Computing and estimating the volume of the solution space of SMT(LA) constraints ⋮ Computation of dilated Kronecker coefficients ⋮ Exact sampling and counting for fixed-margin matrices ⋮ Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients ⋮ The combinatorics of interval vector polytopes ⋮ On the occurrence probability of local binary patterns: a theoretical study ⋮ Multi-collinear splitting kernels for track function evolution ⋮ Symmetrically constrained compositions ⋮ Ehrhart tensor polynomials ⋮ On Ehrhart polynomials and probability calculations in voting theory ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems ⋮ Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration ⋮ Computing with an algebraic-perturbation variant of Barvinok's algorithm ⋮ Integer programming, Barvinok's counting algorithm and Gomory relaxations. ⋮ An example of probability computations under the IAC assumption: the stability of scoring rules ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms ⋮ Counting Solutions of Integer Programs Using Unrestricted Subtree Detection ⋮ A Euclid style algorithm for MacMahon's partition analysis ⋮ Computing the integer programming gap ⋮ Enumerating Projections of Integer Points in Unbounded Polyhedra ⋮ Probability calculations under the IAC hypothesis ⋮ FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension ⋮ Counting with rational generating functions ⋮ An approximation algorithm for box abstraction of transition systems on real state spaces ⋮ Ehrhart series and lattice triangulations ⋮ Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra ⋮ Synthetic two-way contingency tables that preserve conditional frequencies ⋮ Armchair or Zigzag? A tool for characterizing graphene edge ⋮ On the complexity of computing Kronecker coefficients ⋮ The many aspects of counting lattice points in polytopes ⋮ Volume Computation for Boolean Combination of Linear Arithmetic Constraints ⋮ Enhancing SMT-based weighted model integration by structure awareness ⋮ Short rational generating functions for lattice point problems ⋮ On the enumeration of certain weighted graphs ⋮ Polyhedral circuits and their applications ⋮ A generating function for all semi-magic squares and the volume of the Birkhoff polytope ⋮ Rational polyhedral outer-approximations of the second-order cone ⋮ Probabilities of electoral outcomes: from three-candidate to four-candidate elections ⋮ Computing the Ehrhart quasi-polynomial of a rational simplex ⋮ Graded Betti numbers of good filtrations ⋮ LattE ⋮ MacMahon partition analysis and the Poincaré series of the algebras of invariants of ternary and quaternary forms ⋮ Quantitative static analysis of communication protocols using abstract Markov chains ⋮ Ehrhart Polynomials and Successive Minima ⋮ Reachability analysis of low-order discrete state reaction networks obeying conservation laws ⋮ Ehrhart polynomials of matroid polytopes and polymatroids ⋮ Random sampling of contingency tables via probabilistic divide-and-conquer ⋮ Computing algebraic numbers of bounded height ⋮ A computational study of integer programming algorithms based on Barvinok's rational functions ⋮ Computing topological zeta functions of groups, algebras, and modules, I ⋮ Computing rational powers of monomial ideals ⋮ Computing the integer hull of convex polyhedral sets ⋮ Finitely many smooth \(d\)-polytopes with \(n\) lattice points ⋮ Fibers of multi-way contingency tables given conditionals: relation to marginals, cell bounds and Markov bases ⋮ Sparse representation of vectors in lattices and semigroups

Uses Software

Cites Work

This page was built for publication: Effective lattice point counting in rational convex polytopes