Abstract
This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function h. Our technique is based on a refinement of an algorithm of A. Barvinok in the unweighted case (i.e., h≡1). In contrast to Barvinok’s method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach, we report on computational experiments which show that even our simple implementation can compete with state-of-the-art software.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
G.E. Andrews, P. Paule, MacMahon’s dream, SFB-report 2006-26, RISC Linz SFB 013, September 2006.
V. Baldoni, N. Berline, M. Vergne, Local Euler–Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes, Contemp. Math. 452, 15–33 (2008).
V. Baldoni, N. Berline, J.A. De Loera, M. Köppe, M. Vergne, Maple programs accompanying the manuscript. Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. http://www.math.ucdavis.edu/~latte/topweightedehrhart-maple/, 2010.
V. Baldoni, N. Berline, M. Köppe, M. Vergne, Intermediate sums on polyhedra: Computation and real Ehrhart theory, eprint arXiv:1011.6002 [math.CO], 2010.
V. Baldoni, N. Berline, M. Köppe, M. Vergne, Computation of Barvinok valuations of polyhedra, Manuscript, unpublished, 2011.
V. Baldoni, N. Berline, J.A. De Loera, M. Köppe, M. Vergne, How to integrate a polynomial over a simplex, Math. Comput. 80(273), 297–325 (2011).
A.I. Barvinok, Computation of exponential integrals. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) Teor. Slozhn. Vychisl. 5, 149–162, 175–176 (1991), translation in J. Math. Sci. 70(4), 1934–1943 (1994).
A.I. Barvinok, Partition functions in optimization and computational problems. Algebra Anal. 4, 3–53 (1992), translation in St. Petersburg Math. J. 4(1), 1–49 (1993)
A.I. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, Discrete Comput. Geom. 12, 35–48 (1994).
A.I. Barvinok, Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19, 769–779 (1994).
A.I. Barvinok, Computing the Ehrhart quasi-polynomial of a rational simplex, Math. Comput. 75(255), 1449–1466 (2006).
A.I. Barvinok, Integer Points in Polyhedra, Zürich Lectures in Advanced Mathematics (European Mathematical Society (EMS), Zürich, 2008).
A.I. Barvinok, J.E. Pommersheim, An algorithmic theory of lattice points in polyhedra, in New Perspectives in Algebraic Combinatorics, ed. by L.J. Billera, A. Björner, C. Greene, R.E. Simion, R.P. Stanley, Math. Sci. Res. Inst. Publ., vol. 38 (Cambridge Univ. Press, Cambridge, 1999), pp. 91–147.
M. Beck, S. Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, Undergraduate Texts in Mathematics (Springer, Berlin, 2007).
N. Berline, M. Brion, M. Vergne, A Poisson summation formula for piecewise polynomial functions, Manuscript, unpublished, 2010.
A. Björner, L. Lovász, A.C.C. Yao, Linear decision trees: volume estimates and topological bounds, in Proc. 24th Ann. ACM Symp. on Theory of Computing (1992), pp. 170–177.
D. Bremner, K. Fukuda, A. Marzetta, Primal–dual methods for vertex and facet enumeration, Discrete Comput. Geom. 20, 333–357 (1998). doi:10.1007/PL00009389.
M. Brion, Points entiers dans les polyèdres convexes, Ann. Sci. École Norm. Sup. 21(4), 653–663 (1988).
M. Brion, M. Vergne, Lattice points in simple polytopes, J. Am. Math. Soc. 10(2), 371–392 (1997).
M. Brion, M. Vergne, Residue formulae, vector partition functions and lattice points in rational polytopes, J. Am. Math. Soc. 10, 797–833 (1997).
B. Chen, Lattice points, Dedekind sums, and Ehrhart polynomials of lattice polyhedra, Discrete Comput. Geom. 28(2), 175–199 (2002). MR 1920138 (2003g:52019).
Y. Chen, I. Dinwoodie, A. Dobra, M. Huber, Lattice points, contingency tables, and sampling, Contemp. Math. 374, 65–78 (2005).
J.A. De Loera, The many aspects of counting lattice points in polytopes, Math. Semesterber. 52(2), 175–195 (2005). MR 2159956 (2006c:52015).
J.A. De Loera, R. Hemmecke, J. Tauzer, R. Yoshida, Effective lattice point counting in rational convex polytopes, J. Symb. Comput. 38(4), 1273–1302 (2004).
J.A. De Loera, R. Hemmecke, M. Köppe, R. Weismantel, Integer polynomial optimization in fixed dimension, Math. Oper. Res. 31(1), 147–153 (2006).
J.A. De Loera, J. Rambau, F. Santos, Triangulations: Structures for Algorithms and Applications, 1st edn., Algorithms and Computation in Mathematics, vol. 25 (Springer, Berlin, 2010).
P. Diaconis, A. Gangolli, Rectangular arrays with fixed margins, in Discrete Probability and Algorithms (Minneapolis 1993). IMA Series, vol. 72 (Springer, New York, 1995), pp. 15–41.
H. Edelsbrunner, E.P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, in Proceedings of the Fourth Annual Symposium on Computational Geometry, Urbana, IL, 1988 (ACM, New York, 1988), pp. 118–133. MR 1213465.
R. Kannan, A. Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8(4), 499–507 (1979).
M. Köppe, A primal Barvinok algorithm based on irrational decompositions, SIAM J. Discrete Math. 21(1), 220–236 (2007).
M. Köppe, LattE macchiato, version 1.2-mk-0.9.3, an improved version of De Loera et al.’s LattE program for counting integer points in polyhedra with variants of Barvinok’s algorithm, Available from URL http://www.math.ucdavis.edu/~mkoeppe/latte/, 2008.
D. Micciancio, S. Goldwasser, Complexity of Lattice Problems, The Kluwer International Series in Engineering and Computer Science, vol. 671 (Kluwer Academic Publishers, Boston, 2002), A cryptographic perspective. MR 2042139 (2004m:94067).
R. Morelli, Pick’s theorem and the Todd class of a toric variety, Adv. Math. 100(2), 183–231 (1993). MR 1234309 (94j:14048).
S. Verdoolaege, K.M. Woods, Counting with rational generating functions, J. Symb. Comput. 43(2), 75–91 (2008).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Michael Todd.
Rights and permissions
About this article
Cite this article
Baldoni, V., Berline, N., De Loera, J.A. et al. Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra. Found Comput Math 12, 435–469 (2012). https://doi.org/10.1007/s10208-011-9106-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-011-9106-4