Lattice Point Counting and Integration over Convex Polytopes

The papers below discuss algorithms and software for the main functions of LattE: enumeration of all lattice points inside a rational convex polytope, integration of a polynomial over a polytope, and computing coefficients of Ehrhart quasi-polynomials. The common idea of all our "algebraic-analytic" algorithms consist of using rational generating functions to represent either lattice point sets or integrals of functions over polyhedral regions. These algorithms are implemented in LattE, which was the first computer implementation of A. Barvinok's algorithm for unimodular cone decomposition.

Lattice Point Counting

The very first complete paper describing LattE is Effective Lattice Point Counting in Rational Convex Polytopes by J. A. De Loera, R. Hemmecke, J. Tauzer, and R. Yoshida, Journal of Symbolic Computation 38 no. 4 (2004) pp. 1273-1302 doi:10.1016/j.jsc.2003.04.003

• Counting Integer Flows in Networks by W. Baldoni-Silva, J. A. De Loera, and M. Vergne, Foundations of Computational Mathematics 4 no. 3 (2004) pp. 277-314 doi:10.1007/s10208-003-0088-8
• Total Residues for Counting Lattice Points in Unimodular Polytopes
• Polyhedral Cones of Magic Cubes and Squares by M. Ahmed, J. De Loera, and R. Hemmecke, Discrete and Computational Geometry 25 (2003) pp. 25-41 doi:10.1007/978-3-642-55566-4_2

Primal Variants of Barvinok's Algorithm

• A primal Barvinok algorithm based on irrational decompositions SIAM Journal on Discrete Mathematics 21 no. 1 (2007) pp. 220–236 doi:10.1137/060664768

Application of Algebraic-Symbolic Counting Algorithms in LattE

• Contingency Tables
• The Kostant partition function for root systems

Integration

• How to integrate polynomials over simplices by V. Baldoni, N. Berline, J. A. De Loera, M. Köppe, and M. Vergne, Mathematics of Computation 80, 273 (2011) pp. 297-325 doi:10.1090/S0025-5718-2010-02378-6
• Software for exact integration of polynomials over polytopes by J. A. De Loera, B. Dutra, M. Koeppe, S. Moreinis, G. Pinto, and J. Wu, Computational Geometry: Theory and Applications 46 no. 3 (2013) pp. 232–252, doi:10.1016/j.comgeo.2012.09.001 (The computational results and the online supplement can be downloaded here.)

Highest Coefficients of Weighted Ehrhart Quasi-Polynomials

• Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra by V. Baldoni, N. Berline, J. A. De Loera, M. Köppe, and M. Vergne, Foundations of Computational Mathematics 12 no. 4 (2012) pp. 435-469 doi:10.1007/s10208-011-9106-4
• Intermediate sums on polyhedra: Computation and real Ehrhart theory by V. Baldoni, N. Berline, M. Köppe, and M. Vergne, Mathematika 59 no. 1 (2013) pp. 1–22, doi:10.1112/S0025579312000101
• Intermediate Sums on Polyhedra II: Bidegree and Poisson Formula by V. Baldoni, N. Berline, J. A. De Loera, M. Köppe, and M. Vergne, eprint arXiv:1404.0065 [math.CO], 2014
• Three Ehrhart Quasi-polynomials by V. Baldoni, N. Berline, J. A. De Loera, M. Köppe, and M. Vergne, eprint arXiv:1410.8632 [math.CO], 2014
• Top degree coefficients of the denumerant by V. Baldoni, N. Berline, J. A. De Loera, B. Dutra, M. Köppe, and M. Vergne, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS proc. AS, Discrete Mathematics and Theoretical Computer Science (DMTCS), 2013, pp. 1149–1160
• Coefficients of Sylvester’s denumerant by V. Baldoni, N. Berline, J. A. De Loera, B. Dutra, M. Köppe, and M. Vergne, eprint arXiv:1312.7147 [math.CO], 2013

Research Monograph and Textbook

Algebraic and Geometric Ideas in the Theory of Discrete Optimization (2012, xx + 313 pages) by J.A. De Loera, R. Hemmecke and M. Köppe. This book presents recent advances in the theory of discrete optimization, particularly those arising from algebraic geometry, commutative algebra, convex and discrete geometry. The material within is not yet well known, but it is accessible to students of mathematics, computer science, algorithms or operations research at the advanced undergraduate level and beyond. In particular, part III: Generating Function Methods, deals with many ideas core to the main LattE functions. See the contents for more.