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
Some key papers and websites that supported further development are
Primal Variants of Barvinok's Algorithm
The theory behind the development of LattE macchiato was presented by M. Köppe in
Application of Algebraic-Symbolic Counting Algorithms in LattE
Professor De Loera presents two interesting applications of counting lattice points:
The next two papers explore how to integrate polynomials over polytopes, as implemented in LattE integrale version 1.5.
- 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
- 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
The following paper explains how to compute the highest coefficients
of weighted Ehrhart quasi-polynomials as step-polynomials, as
implemented in LattE integrale version 1.6.
- 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
- 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,
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
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.