How to integrate a polynomial over a simplex

Baldoni, Velleda; Berline, Nicole; De Loera, Jesus; Köppe, Matthias; Vergne, Michèle

doi:10.1090/S0025-5718-2010-02378-6

How to integrate a polynomial over a simplex
HTML articles powered by AMS MathViewer

by Velleda Baldoni, Nicole Berline, Jesus A. De Loera, Matthias Köppe and Michèle Vergne PDF

Math. Comp. 80 (2011), 297-325 Request permission

Abstract:

This paper starts by settling the computational complexity of the problem of integrating a polynomial function $f$ over a rational simplex. We prove that the problem is $\mathrm {NP}$-hard for arbitrary polynomials via a generalization of a theorem of Motzkin and Straus. On the other hand, if the polynomial depends only on a fixed number of variables, while its degree and the dimension of the simplex are allowed to vary, we prove that integration can be done in polynomial time. As a consequence, for polynomials of fixed total degree, there is a polynomial time algorithm as well. We explore our algorithms with some experiments. We conclude the article with extensions to other polytopes and discussion of other available methods.

References

J. Alexander and A. Hirschowitz, Polynomial interpolation in several variables, J. Algebraic Geom. 4 (1995), no. 2, 201–222. MR 1311347
V. Baldoni, N. Berline, J. A. De Loera, M. Köppe, and M. Vergne, Maple programs accompanying the manuscript How to integrate a polynomial over a simplex, http://www.math.ucdavis.edu/~mkoeppe/art/pisa-integration-experiments/, 2008.
A. I. Barvinok, Calculation of exponential integrals, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 192 (1991), no. Teor. Slozhn. Vychisl. 5, 149–162, 175–176 (Russian, with English summary); English transl., J. Math. Sci. 70 (1994), no. 4, 1934–1943. MR 1118837, DOI 10.1007/BF02112432
A. I. Barvinok, Exponential integrals and sums over convex polyhedra, Funktsional. Anal. i Prilozhen. 26 (1992), no. 2, 64–66 (Russian); English transl., Funct. Anal. Appl. 26 (1992), no. 2, 127–129. MR 1173086, DOI 10.1007/BF01075276
A. I. Barvinok, Statistical sums in optimization and computational problems, Algebra i Analiz 4 (1992), no. 1, 3–53 (Russian); English transl., St. Petersburg Math. J. 4 (1993), no. 1, 1–49. MR 1171953
Nicole Berline and Michèle Vergne, Local Euler-Maclaurin formula for polytopes, Mosc. Math. J. 7 (2007), no. 3, 355–386, 573 (English, with English and Russian summaries). MR 2343137, DOI 10.17323/1609-4514-2007-7-3-355-386
Nicole Berline and Michèle Vergne, Local Euler-Maclaurin formula for polytopes, Mosc. Math. J. 7 (2007), no. 3, 355–386, 573 (English, with English and Russian summaries). MR 2343137, DOI 10.17323/1609-4514-2007-7-3-355-386
Nicole Berline, Ezra Getzler, and Michèle Vergne, Heat kernels and Dirac operators, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 298, Springer-Verlag, Berlin, 1992. MR 1215720, DOI 10.1007/978-3-642-58088-8
A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Probability and Mathematical Statistics, Academic Press, Inc., Orlando, FL, 1986. MR 856019
J. Brachat, P. Comon, B. Mourrain, and E. Tsigaridas, Symmetric tensor decomposition, arXiv:\penalty0 0901.3706v2 [cs.SC], 2009.
M. C. Brambilla and G. Ottaviani, On the Alexander–Hirschowitz theorem, e-print arXiv:math.AG/0701409v2, 2007.
Graham Brightwell and Peter Winkler, Counting linear extensions, Order 8 (1991), no. 3, 225–242. MR 1154926, DOI 10.1007/BF00383444
Michel Brion, Points entiers dans les polyèdres convexes, Ann. Sci. École Norm. Sup. (4) 21 (1988), no. 4, 653–663 (French). MR 982338
Michel Brion and Michèle Vergne, Lattice points in simple polytopes, J. Amer. Math. Soc. 10 (1997), no. 2, 371–392. MR 1415319, DOI 10.1090/S0894-0347-97-00229-4
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
R. Cools and A. Haegemans, Algorithm 824: CUBPACK: a package for automatic cubature; framework description., ACM Trans. Math. Software 29 (2003), no. 3, 287–296.
Wolfgang Dahmen, On multivariate $B$-splines, SIAM J. Numer. Anal. 17 (1980), no. 2, 179–191. MR 567267, DOI 10.1137/0717017
J. A. De Loera, J. Rambau, and F. Santos, Triangulations: Structures for algorithms and applications, Algorithms and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 2010.
M. E. Dyer and A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM J. Comput. 17 (1988), no. 5, 967–974. MR 961051, DOI 10.1137/0217060
G. Elekes, A geometric inequality and the complexity of computing volume, Discrete Comput. Geom. 1 (1986), no. 4, 289–292. MR 866364, DOI 10.1007/BF02187701
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
Alan Genz and Ronald Cools, An adaptive numerical cubature algorithm for simplices, ACM Trans. Math. Software 29 (2003), no. 3, 297–308. MR 2002733, DOI 10.1145/838250.838254
Axel Grundmann and H. M. Möller, Invariant integration formulas for the $n$-simplex by combinatorial methods, SIAM J. Numer. Anal. 15 (1978), no. 2, 282–290. MR 488881, DOI 10.1137/0715019
Ravindran Kannan and Achim Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (1979), no. 4, 499–507. MR 573842, DOI 10.1137/0208040
Leonid Khachiyan, Complexity of polytope volume computation, New trends in discrete and computational geometry, Algorithms Combin., vol. 10, Springer, Berlin, 1993, pp. 91–101. MR 1228040, DOI 10.1007/978-3-642-58043-7_{5}
Jean B. Lasserre, Integration on a convex polytope, Proc. Amer. Math. Soc. 126 (1998), no. 8, 2433–2441. MR 1459132, DOI 10.1090/S0002-9939-98-04454-2
Jean B. Lasserre and Konstantin E. Avrachenkov, The multi-dimensional version of $\int ^b_a x^p dx$, Amer. Math. Monthly 108 (2001), no. 2, 151–154. MR 1818188, DOI 10.2307/2695528
Monique Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York, 2009, pp. 157–270. MR 2500468, DOI 10.1007/978-0-387-09686-5_{7}
Jim Lawrence, Polytope volume computation, Math. Comp. 57 (1991), no. 195, 259–271. MR 1079024, DOI 10.1090/S0025-5718-1991-1079024-2
Shaowei Lin, Bernd Sturmfels, and Zhiqiang Xu, Marginal likelihood integrals for mixtures of independence models, J. Mach. Learn. Res. 10 (2009), 1611–1631. MR 2534873
Guillermo Matera, Integration of multivariate rational functions given by straight-line programs, Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995) Lecture Notes in Comput. Sci., vol. 948, Springer, Berlin, 1995, pp. 347–364. MR 1448176, DOI 10.1007/3-540-60114-7_{2}7
Charles A. Micchelli, Mathematical aspects of geometric modeling, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 65, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995. MR 1308048, DOI 10.1137/1.9781611970067
T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canadian J. Math. 17 (1965), 533–540. MR 175813, DOI 10.4153/CJM-1965-053-6
Luis Rademacher, Approximating the centroid is hard, Computational geometry (SCG’07), ACM, New York, 2007, pp. 302–305. MR 2469178, DOI 10.1145/1247069.1247123
Murray Schechter, Integration over a polyhedron: an application of the Fourier-Motzkin elimination method, Amer. Math. Monthly 105 (1998), no. 3, 246–251. MR 1615560, DOI 10.2307/2589079
Z. Xu, Multivariate splines and polytopes, arXiv:\penalty0 0806.1127v3, 2009.
Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1
O. C. Zienkiewicz and R. L. Taylor, The finite element method, McGraw-Hill, London, 1988.