Algebraic Unimodular Counting
Preprint
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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- TOPCOM: TRIANGULATIONS OF POINT CONFIGURATIONS AND ORIENTED MATROIDS2002
- Fast Unimodular CountingCombinatorics, Probability and Computing, 2000
- Algebraic algorithms for sampling from conditional distributionsThe Annals of Statistics, 1998
- Stochastic Simulation on Integer Constraint SetsSIAM Journal on Optimization, 1998
- On Barvinok's Algorithm for Counting Lattice Points in Fixed DimensionMathematics of Operations Research, 1997
- On vector partition functionsJournal of Combinatorial Theory, Series A, 1995
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is FixedMathematics of Operations Research, 1994
- Duality and Minors of Secondary PolyhedraJournal of Combinatorial Theory, Series B, 1993
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedraDiscrete & Computational Geometry, 1992
- The Kostant partition function for simple Lie algebrasJournal of Mathematical Physics, 1984