Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

How to integrate a polynomial over a simplex


Authors: Velleda Baldoni, Nicole Berline, Jesus A. De Loera, Matthias Köppe and Michèle Vergne
Journal: Math. Comp. 80 (2011), 297-325
MSC (2010): Primary 68W30; Secondary 52B55
DOI: https://doi.org/10.1090/S0025-5718-2010-02378-6
Published electronically: July 14, 2010
Table supplement: Appendix A
MathSciNet review: 2728981
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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 $ B$-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 $ n$-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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 52B55

Retrieve articles in all journals with MSC (2010): 68W30, 52B55


Additional Information

Velleda Baldoni
Affiliation: Dipartimento di Matematica, Università degli studi di Roma “Tor Vergata”, Via della ricerca scientifica 1, I-00133, Italy
Email: baldoni@mat.uniroma2.it

Nicole Berline
Affiliation: Centre de Mathématiques Laurent Schwartz, École Polytechnique, 91128 Palaiseau Cedex, France
Email: nicole.berline@math.polytechnique.fr

Jesus A. De Loera
Affiliation: Department of Mathematics, University of California, Davis, One Shields Avenue, Davis, California 95616
Email: deloera@math.ucdavis.edu

Matthias Köppe
Affiliation: Department of Mathematics, University of California, Davis, One Shields Avenue, Davis, California 95616
Email: mkoeppe@math.ucdavis.edu

Michèle Vergne
Affiliation: Institut de Mathématiques de Jussieu, 175 rue du Chevaleret, 75103 Paris, France
Email: vergne@math.jussieu.fr

DOI: https://doi.org/10.1090/S0025-5718-2010-02378-6
Received by editor(s): February 16, 2009
Received by editor(s) in revised form: September 25, 2009
Published electronically: July 14, 2010
Article copyright: © Copyright 2010 American Mathematical Society

American Mathematical Society