Effective lattice point counting in rational convex polytopes

DOI10.1016/J.JSC.2003.04.003zbMATH Open1137.52303OpenAlexW2033084216MaRDI QIDQ2643564FDOQ2643564

Authors: 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

Recommendations

• The many aspects of counting lattice points in polytopes
• An Alternative Algorithm for Counting Lattice Points in a Convex Polytope
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• A Primal Barvinok Algorithm Based on Irrational Decompositions
• Computing convex hulls and counting integer points with \texttt{polymake}

zbMATH Keywords

lattice pointsgenerating functionsrational functionsBarvinok's algorithmEhrhart quasi-polynomialsconvex rational polyhedraenumeration of lattice points

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) 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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Ehrhart polynomial of the Birkhoff polytope
• Decompositions of Rational Convex Polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotics of multivariate sequences. I: Smooth points of the singular variety
• Geometric algorithms and combinatorial optimization.
• Integer Programming with a Fixed Number of Variables
• Points entiers dans les polyèdres convexes
• Title not available (Why is that?)
• Fast Unimodular Counting
• Title not available (Why is that?)
• The Generalized Basis Reduction Algorithm
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming
• Title not available (Why is that?)
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• Algebraic unimodular counting
• Convex polytopes all of whose reverse lexicographic initial ideals are squarefree
• Title not available (Why is that?)
• Short rational generating functions for lattice point problems
• Short rational functions for toric algebra and applications
• Title not available (Why is that?)
• Representations of integers by linear forms in nonnegative integers
• Title not available (Why is that?)
• Counting lattice points by means of the residue theorem
• Title not available (Why is that?)
• Non-standard approaches to integer programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Kostant partition function for simple Lie algebras
• Ubiquity of Kostka polynomials
• Title not available (Why is that?)
• Solving the knapsack problem via \(\mathbb Z\)-transform

Cited In (88)

• MacMahon partition analysis and the Poincaré series of the algebras of invariants of ternary and quaternary forms
• Polytope volume by descent in the face lattice and applications in social choice
• FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
• Computing rational powers of monomial ideals
• Computing the Ehrhart quasi-polynomial of a rational simplex
• The combinatorics of interval vector polytopes
• Title not available (Why is that?)
• Exact sampling and counting for fixed-margin matrices
• Petri Net Reductions for Counting Markings
• A generating function for all semi-magic squares and the volume of the Birkhoff polytope
• A Primal Barvinok Algorithm Based on Irrational Decompositions
• Armchair or Zigzag? A tool for characterizing graphene edge
• On the pseudo-periodicity of the integer hull of parametric convex polygons
• Quantifying software reliability via model-counting
• On the enumeration of certain weighted graphs
• Ehrhart tensor polynomials
• Computing algebraic numbers of bounded height
• Column basis reduction and decomposable knapsack problems
• Sparse representation of vectors in lattices and semigroups
• Volume Computation for Boolean Combination of Linear Arithmetic Constraints
• Quantitative static analysis of communication protocols using abstract Markov chains
• The subdivision of large simplicial cones in Normaliz
• On the complexity of computing Kronecker coefficients
• Random sampling of contingency tables via probabilistic divide-and-conquer
• Polynomial time reachability analysis in discrete state chemical reaction networks obeying conservation laws
• Ehrhart Polynomials and Successive Minima
• Counting integral points in polytopes via numerical analysis of contour integration
• Probabilities of electoral outcomes: from three-candidate to four-candidate elections
• Counting Solutions of Integer Programs Using Unrestricted Subtree Detection
• Computing the integer programming gap
• Lattice point enumeration and applications
• Title not available (Why is that?)
• Enumerating projections of integer points in unbounded polyhedra
• Integer programming, Barvinok's counting algorithm and Gomory relaxations.
• An example of probability computations under the IAC assumption: the stability of scoring rules
• Finitely many smooth \(d\)-polytopes with \(n\) lattice points
• Computing the integer hull of convex polyhedral sets
• Computing convex hulls and counting integer points with \texttt{polymake}
• Polyhedral circuits and their applications
• Rational polyhedral outer-approximations of the second-order cone
• Computing and estimating the volume of the solution space of SMT(LA) constraints
• On lattice point counting in \(\varDelta\)-modular polyhedra
• The many aspects of counting lattice points in polytopes
• LattE
• A computational study of integer programming algorithms based on Barvinok's rational functions
• On Ehrhart polynomials and probability calculations in voting theory
• Synthetic two-way contingency tables that preserve conditional frequencies
• Probability calculations under the IAC hypothesis
• Counting with rational generating functions
• On the occurrence probability of local binary patterns: a theoretical study
• Counting integer flows in networks
• Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
• A Euclid style algorithm for MacMahon's partition analysis
• Short rational functions for toric algebra and applications
• Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients
• Short rational generating functions for lattice point problems
• Computing topological zeta functions of groups, algebras, and modules. I
• Polyhedral omega: a new algorithm for solving linear Diophantine systems
• Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
• Enumerating lattice 3-polytopes
• Symmetrically constrained compositions
• Ehrhart polynomials of matroid polytopes and polymatroids
• Computing with an algebraic-perturbation variant of Barvinok's algorithm
• An Alternative Algorithm for Counting Lattice Points in a Convex Polytope
• Computation of dilated Kronecker coefficients
• Ehrhart series and lattice triangulations
• Fibers of multi-way contingency tables given conditionals: relation to marginals, cell bounds and Markov bases
• On Dedekind's problem for complete simple games
• A chaotic lattice field theory in one dimension
• Reachability analysis of low-order discrete state reaction networks obeying conservation laws
• Sampling lattice points in a polytope: a Bayesian biased algorithm with random updates
• Computing points of bounded height in projective space over a number field
• A combinatorial approach to Frobenius numbers of some special sequences
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• An approximation algorithm for box abstraction of transition systems on real state spaces
• Estimating the volume of the solution space of SMT(LIA) constraints by a flat histogram method
• Multi-collinear splitting kernels for track function evolution
• Title not available (Why is that?)
• How to find the convex hull of all integer points in a polyhedron?
• Experimental study of the Ehrhart interpolation polytope
• On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
• 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
• Enhancing SMT-based weighted model integration by structure awareness
• Graded Betti numbers of good filtrations
• Computing Galois groups of Ehrhart polynomials in OSCAR
• Counting the integer points of parametric polytopes: a Maple implementation

Uses Software

• cdd
• Normaliz
• NTL

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

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