Algebraic unimodular counting

DOI10.1007/S10107-003-0383-9MaRDI QIDQ1424267zbMATH OpenOpenAlexFDO

Authors Jesús A. De Loera, Bernd Sturmfels

Publication date 11 March 2004

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0104286, https://www.escholarship.org/uc/item/666982kh

zbMATH Keywords

contingency tablespartition functionunimodular counting

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: We study algebraic algorithms for expressing the number of non-negative integer solutions to a unimodular system of linear equations as a function of the right hand side. Our methods include Todd classes of toric varieties via Gr"obner bases, and rational generating functions as in Barvinok's algorithm. We report polyhedral and computational results for two special cases: counting contingency tables and Kostant's partition function.

Review text

The vector partition function \(\Phi_A(b) = \#\{x: Ax = b, x \geq 0, x \text{ integer}\}\) is studied, where \(A\) is a \(d \times n\) unimodular matrix and \(b\) is a variable integer vector. Unimodular counting refers to preprocessing \(A\) and generating the polynomials for \(\Phi_A\) on the domains of polynomiality (chambers). Two methods for finding a chamber that contains \(b\) and for enumerating all chambers are given. The first uses Gröbner bases, the second is based on Barvinok's polynomial time algorithm for counting lattice points in rational polytopes of fixed dimension. Results on two special cases, counting contingency tables and the Kostant partition function, are given.

Recommendations

• Algebraic model counting
• scientific article; zbMATH DE number 863490
• Counting finite-dimensional algebras over finite field
• Counting algebraic units with bounded height
• Unimodular integer circulants
• scientific article; zbMATH DE number 428989
• scientific article; zbMATH DE number 3882507
• A property of algebraic univoque numbers
• Counting commutativities in finite algebraic systems
• Algebraic theory of numbers

Cited in

(19)

• Counting colorings on varieties
• The Ehrhart polynomial of the Birkhoff polytope
• The partial-fractions method for counting solutions to integral linear systems
• A divide-and-conquer algorithm for generating Markov bases of multi-way tables
• A vector partition function for the multiplicities of \(\mathfrak{sl}_k\mathbb C\)
• Counting integer points of flow polytopes
• On Kostant's weight \(q\)-multiplicity formula for \(\mathfrak{sl}_4(\mathbb{C})\)
• Multivariate volume, Ehrhart, and \(h^\ast \)-polynomials of polytropes
• Root cones and the resonance arrangement
• Counting with rational generating functions
• Effective lattice point counting in rational convex polytopes
• Exact sampling and counting for fixed-margin matrices
• Fast Unimodular Counting
• scientific article; zbMATH DE number 863490 (Why is no real title available?)
• An invitation to the generalized saturation conjecture
• Approximating the volume of tropical polytopes is difficult
• Asymptotics of multivariate sequences. IV: Generating functions with poles on a hyperplane arrangement
• External columns and chambers of vector partition functions
• A property of algebraic univoque numbers

Describes a project that uses

Uses Software

• Macaulay2

This page was built for publication: Algebraic unimodular counting

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