LattE: Lattice point enumeration and applications to multiway contingency tables.Algebra & Discrete Mathematics
|Ruriko Yoshida, Math UC Davis
|Wed, Jan 9 2002, 1:10PM
We are presenting polyhedral-algebraic algorithms to count the number of contingency tables with fixed given margins. We will describe our program LattE, the first implementation which applies Barvinok's cone decomposition and the symbolic algebra of power series to the algorithms. Barvinok's cone decomposition is the algorithm that can decompose any cone into unimodular cones. If we fix the dimension, Barvinok's cone decomposition runs in polynomial time. After we decompose each vertex cone of a given polytope into unimodular cones, we can write the formal power series and count the number of lattice points inside the given polytope. This decomposition can be used to write Hilbert-function like generating functions counting lattice points at dilations of the polytope (Ehrhart polynomials).