Mathematics of Computation

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

How to integrate a polynomial over a simplex

Author(s): Velleda Baldoni; Nicole Berline; Jesus A. De Loera; Matthias Köppe; Michèle Vergne.
Journal: Math. Comp. 80 (2011), 297-325.
MSC (2010): Primary 68W30; Secondary 52B55
Posted: July 14, 2010
Table supplement: Appendix A
MathSciNet review: 2728981
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

Abstract: This paper starts by settling the computational complexity of the problem of integrating a polynomial function 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:

1.: J. Alexander and A. Hirschowitz, Polynomial interpolation in several variables, J. Algebraic Geom. 4 (1995), 201-222. MR 1311347 (96f:14065)
2.: 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.
3.: A. I. Barvinok, Computation of exponential integrals, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) Teor. Slozhn. Vychisl. 5 (1991), 149-162, 175-176, translation in J. Math. Sci. 70 (1994), no. 4, 1934-1943. MR 1118837 (92i:65228)
4.: -, Exponential integrals and sums over convex polyhedra (in Russian), Funktsional. Anal. i Prilozhen. 26 (1992), no. 2, 64-66, translated in Funct. Anal. Appl. 26 (1992), no. 2, pp. 127-129. MR 1173086 (93g:32052)
5.: -, Partition functions in optimization and computational problems, Algebra i Analiz 4 (1992), 3-53, translation in St. Petersburg Math. J. 4 (1993), no. 1, pp. 1-49. MR 1171953 (93f:90131)
6.: N. Berline and M. Vergne, Local Euler-Maclaurin formula for polytopes, Moscow Math. J. 7 (2007), 355-386. MR 2343137 (2008k:52026)
7.: -, Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes, Contemporary Mathematics 452 (2008), 15-33. MR 2343137 (2008k:52026)
8.: N. Berline, E. Getzler, and M. Vergne, Heat kernels and Dirac operators, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 298, Springer-Verlag, Berlin, 1992. MR 1215720 (94e:58130)
9.: A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Academic Press, Orlando, Florida, 1986. MR 856019 (87m:60118)
10.: J. Brachat, P. Comon, B. Mourrain, and E. Tsigaridas, Symmetric tensor decomposition, arXiv: 0901.3706v2 [cs.SC], 2009.
11.: M. C. Brambilla and G. Ottaviani, On the Alexander-Hirschowitz theorem, e-print arXiv:math.AG/0701409v2, 2007.
12.: G. Brightwell and P. Winkler, Counting linear extensions, Order 8 (1991), no. 3, 225-242. MR 1154926 (93b:06002)
13.: M. Brion, Points entiers dans les polyédres convexes, Ann. Sci. École Norm. Sup. 21 (1988), no. 4, 653-663. MR 982338 (90d:52020)
14.: M. Brion and M. Vergne, Lattice points in simple polytopes, J. Amer. Math. Soc. 10 (1997), no. 2, 371-392. MR 1415319 (98a:11132)
15.: P. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften, no. 315, Springer, Berlin, 1997. MR 1440179 (99c:68002)
16.: 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.
17.: W. Dahmen, On multivariate -splines, SIAM J. Numer. Anal. 17 (1980), no. 2, 179-191. MR 567267 (81c:41020)
18.: 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.
19.: 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 (90f:68077)
20.: G. Elekes, A geometric inequality and the complexity of computing volume, Discrete Comput. Geom. 1 (1986), no. 4, 289-292. MR 866364 (87k:68138)
21.: M. R. Garey and D. S. Johnson, Computers and intractibility: A guide to the theory of NP-completeness, W. H. Freeman and Co., San Francisco, California, 1979. MR 519066 (80g:68056)
22.: A. Genz and R. Cools, An adaptive numerical cubature algorithm for simplices, ACM Trans. Math. Software 29 (2003), no. 3, 297-308. MR 2002733 (2004g:65021)
23.: A. Grundmann and H. M. Möller, Invariant integration formulas for the -simplex by combinatorial methods, SIAM J. Numer. Anal. 15 (1978), 282-290. MR 488881 (81e:41045)
24.: R. Kannan and A. 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 (81k:15002)
25.: L. 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 (94m:68190)
26.: J. B. Lasserre, Integration on a convex polytope, Proceedings of the AMS 126 (1998), no. 8, 2433-2441. MR 1459132 (98j:65016)
27.: J. B. Lasserre and K. Avrachenkov, The multidimensional version of $\int_a^b x^p \mathrm{d}x$ , American Mathematical Monthly 108 (2001), no. 2, 151-154. MR 1818188 (2002g:26015)
28.: M. Laurent, Sums of squares, moment matrices, and optimization over polynomials, In ``Emerging applications of algebraic geometry'' (Minneapolis, Minnesota) (M. Putinar and S. Sullivant, eds.), IMA volumes in Mathematics and its Applications, 2008. MR 2500468
29.: J. Lawrence, Polytope volume computation, Math. Comp. 57 (1991), no. 195, 259-271. MR 1079024 (91j:52019)
30.: S. Lin, B. Sturmfels, and Z. Xu, Marginal likelihood integrals for mixtures of independence models, J. Mach. Learn. Res. 10 (2009), 1611-1631. MR 2534873
31.: G. Matera, Integration of multivariate rational functions given by straight-line programs, Proceedings of the 11th international symposium on applied algebra, algebraic algorithms and error-correcting codes (London), Lecture Notes in Computer Science, vol. 948, Springer, 1995, pp. 347-364. MR 1448176 (98c:68104)
32.: C. 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 (95i:65036)
33.: T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canadian Journal of Mathematics 17 (1965), 533-540. MR 0175813 (31:89)
34.: L. Rademacher, Approximating the centroid is hard, Proceedings of 23th annual ACM Symposium of Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, 2007, pp. 302-305. MR 2469178 (2009m:68104)
35.: M. Schechter, Integration over a polyhedron: An application of the Fourier-Motzkin elimination method, American Mathematical Monthly 105 (1998), no. 3, 246-251. MR 1615560 (99d:15014)
36.: Z. Xu, Multivariate splines and polytopes, arXiv: 0806.1127v3, 2009.
37.: G. M. Ziegler, Lectures on polytopes, Graduate texts in Mathematics, no. 152, Springer, New York, 1995. MR 1311028 (96a:52011)
38.: O. C. Zienkiewicz and R. L. Taylor, The finite element method, McGraw-Hill, London, 1988.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|