Mathematics of Computation

Author(s): Alexander Barvinok.
Journal: Math. Comp. 75 (2006), 1449-1466.
MSC (2000): Primary 52C07; Secondary 05A15, 68R05
Posted: March 10, 2006
Retrieve article in: PDF DVI PostScript

Abstract: We present a polynomial time algorithm to compute any fixed number of the highest coefficients of the Ehrhart quasi-polynomial of a rational simplex. Previously such algorithms were known for integer simplices and for rational polytopes of a fixed dimension. The algorithm is based on the formula relating the

th coefficient of the Ehrhart quasi-polynomial of a rational polytope to volumes of sections of the polytope by affine lattice subspaces parallel to

-dimensional faces of the polytope. We discuss possible extensions and open questions.

1.: W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Math. Ann. 296 (1993), 625-635. MR 1233487 (94k:11075)
2.: A. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, preprint TRITA-MAT-1992-0036 (1992), Royal Institute of Technology, Stockholm.
3.: A. Barvinok, Computing the volume, counting integral points, and exponential sums, Discrete Comput. Geom. 10 (1993), 123-141. MR 1220543 (94d:52005)
4.: A. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994), 769-779. MR 1304623 (96c:52026)
5.: A. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, Discrete Comput. Geom. 12 (1994), 35-48. MR 1280575 (95e:52015)
6.: A. Barvinok and J. Pommersheim, An algorithmic theory of lattice points in polyhedra, New perspectives in algebraic combinatorics (Berkeley, CA, 1996-97), Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 91-147.MR 1731815 (2000k:52014)
7.: A. Barvinok and K. Woods, Short rational generating functions for lattice point problems, J. Amer. Math. Soc. 16 (2003), 957-979. MR 1992831 (2004e:05009)
8.: M. Beck and F. Sottile, Irrational proofs for three theorems of Stanley, preprint arXiv math.CO/0501359, 2005.
9.: R. Bellman, A Brief Introduction to Theta Functions, Athena Series: Selected Topics in Mathematics, Holt Rinehart and Winston, New York, 1961.MR 0125252 (23:A2556)
10.: K. Beyls, M. Bruynooghe, V. Loechner, R. Seghir, and S. Verdoolaege Analytical computation of Ehrhart polynomials: Enabling more compiler analyses and optimizations, Proceedings of the 2004 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, ACM Press, New York, 2004 pp. 248-258; see also http:// www.kotnet.org/ $^\sim$ skimo/barvinok.
11.: J. A. De Loera, R. Hemmecke, J. Tauzer, and R. Yoshida, Effective lattice point counting in rational convex polytopes, J. Symbolic Comput. 38(2004), 1273-1302; see also http:// www.math.ucdavis.edu/ $^\sim$ latte. MR 2094541 (2005i:52020)
12.: J. A. De Loera, R. Hemmecke, M. Köppe, and R. Weismantel, Integer polynomial optimization in fixed dimension, preprint, arXiv: math.OC/0410111, 2004.
13.: R. Diaz and S. Robins, Solid angles, lattice points, and the Fourier decomposition of polytopes, manuscript, 1994.
14.: R. Diaz and S. Robins, The Ehrhart polynomial of a lattice polytope, Ann. of Math. (2) 145 (1997), 503-518; Erratum: 146 (1997), no. 1, 237.MR 1454701 (98e:11117a), MR 1469320 (98e:11117b)
15.: P. Gritzmann and V. Klee, On the complexity of some basic problems in computational convexity. II. Volume and mixed volumes, Polytopes: Abstract, Convex and Computational (Scarborough, ON, 1993), NATO Adv. Sci. Inst. Ser. C. Math. Phys. Sci., vol. 440, Kluwer Acad. Publ., Dordrecht, 1994, pp. 373-466. MR 1322071 (96k:52012)
16.: M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Second edition, Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR 1261419 (95e:90001)
17.: P. D. Lax, Functional Analysis, Pure and Applied Mathematics, Wiley-Interscience, New York, 2002. MR 1892228 (2003a:47001)
18.: J. Matoušek, Lectures on Discrete Geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299 (2003f:52011)
19.: P. McMullen, Lattice invariant valuations on rational polytopes, Arch. Math. (Basel) 31 1978/79, 509-516. MR 0526617 (80d:52011)
20.: P. McMullen, Valuations and dissections, Handbook of Convex Geometry, vol. B, North-Holland, Amsterdam, 1993, pp. 933-988.MR 1243000 (95f:52018)
21.: P. McMullen and R. Schneider, Valuations on convex bodies, Convexity and its Applications, Birkhäuser, Basel, 1983, pp. 170-247. MR 0731112 (85e:52001)
22.: R. Morelli, Pick's theorem and the Todd class of a toric variety, Adv. Math. 100 (1993), 183-231. MR 1234309 (94j:14048)
23.: J. Pommersheim and H. Thomas, Cycles representing the Todd class of a toric variety, J. Amer. Math. Soc. 17 (2004), 983-994. MR 2083474 (2005h:14124)
24.: R. Schneider, Convex Bodies: The Brunn-Minkowski Theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR 1216521 (94d:52007)
25.: A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley $\&$ Sons, Ltd., Chichester, 1986. MR 0874114 (88m:90090)
26.: V. N. Shevchenko, Qualitative Topics in Integer Linear Programming, Translated from the Russian by H. H. McFaden. Translations of Mathematical Monographs, vol. 156, American Mathematical Society, Providence, RI, 1997.MR 1414900 (97m:90001)
27.: R. P. Stanley, Enumerative Combinatorics. Vol. 1, corrected reprint of the 1986 original. Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997.MR 1442260 (98a:05001)

Retrieve articles in Mathematics of Computation with MSC (2000): 52C07, 05A15, 68R05

Alexander Barvinok
Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1043
Email: barvinok@umich.edu

DOI: 10.1090/S0025-5718-06-01836-9
PII: S 0025-5718(06)01836-9
Keywords: Ehrhart quasi-polynomial, rational polytope, valuation, algorithm
Received by editor(s): April 29, 2005
Posted: March 10, 2006
Additional Notes: This research was partially supported by NSF Grant DMS 0400617
Copyright of article: Copyright 2006, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS