×

How to integrate a polynomial over a simplex. (English) Zbl 1216.68120

Summary: 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 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.

MSC:

68Q25 Analysis of algorithms and problem complexity
52B55 Computational aspects related to convexity
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Alexander and A. Hirschowitz, Polynomial interpolation in several variables, J. Algebraic Geom. 4 (1995), no. 2, 201 – 222. · Zbl 0829.14002
[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, 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. · Zbl 0835.65044 · doi:10.1007/BF02112432
[4] 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. · Zbl 0798.32002 · doi:10.1007/BF01075276
[5] 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.
[6] 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). · Zbl 1146.52006
[7] 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). · Zbl 1146.52006
[8] 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. · Zbl 0744.58001
[9] A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Probability and Mathematical Statistics, Academic Press, Inc., Orlando, FL, 1986. · Zbl 0615.60058
[10] J. Brachat, P. Comon, B. Mourrain, and E. Tsigaridas, Symmetric tensor decomposition, arXiv: 0901.3706v2 [cs.SC], 2009. · Zbl 1206.65141
[11] M. C. Brambilla and G. Ottaviani, On the Alexander-Hirschowitz theorem, e-print arXiv:math.AG/0701409v2, 2007. · Zbl 1139.14007
[12] Graham Brightwell and Peter Winkler, Counting linear extensions, Order 8 (1991), no. 3, 225 – 242. · Zbl 0759.06001 · doi:10.1007/BF00383444
[13] Michel Brion, Points entiers dans les polyèdres convexes, Ann. Sci. École Norm. Sup. (4) 21 (1988), no. 4, 653 – 663 (French). · Zbl 0667.52011
[14] Michel Brion and Michèle Vergne, Lattice points in simple polytopes, J. Amer. Math. Soc. 10 (1997), no. 2, 371 – 392. · Zbl 0871.52009
[15] 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. · Zbl 1087.68568
[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. · Zbl 1070.65517
[17] Wolfgang Dahmen, On multivariate \?-splines, SIAM J. Numer. Anal. 17 (1980), no. 2, 179 – 191. · Zbl 0425.41015 · doi:10.1137/0717017
[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. · Zbl 1207.52002
[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. · Zbl 0668.68049 · doi:10.1137/0217060
[20] G. Elekes, A geometric inequality and the complexity of computing volume, Discrete Comput. Geom. 1 (1986), no. 4, 289 – 292. · Zbl 0611.52010 · doi:10.1007/BF02187701
[21] Michael R. Garey and David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. · Zbl 0411.68039
[22] Alan Genz and Ronald Cools, An adaptive numerical cubature algorithm for simplices, ACM Trans. Math. Software 29 (2003), no. 3, 297 – 308. · Zbl 1072.65032 · doi:10.1145/838250.838254
[23] Axel Grundmann and H. M. Möller, Invariant integration formulas for the \?-simplex by combinatorial methods, SIAM J. Numer. Anal. 15 (1978), no. 2, 282 – 290. · Zbl 0376.65013 · doi:10.1137/0715019
[24] 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. · Zbl 0446.65015 · doi:10.1137/0208040
[25] Leonid Khachiyan, Complexity of polytope volume computation, New trends in discrete and computational geometry, Algorithms Combin., vol. 10, Springer, Berlin, 1993, pp. 91 – 101. · Zbl 0789.52016 · doi:10.1007/978-3-642-58043-7_5
[26] Jean B. Lasserre, Integration on a convex polytope, Proc. Amer. Math. Soc. 126 (1998), no. 8, 2433 – 2441. · Zbl 0901.65012
[27] Jean B. Lasserre and Konstantin E. Avrachenkov, The multi-dimensional version of \int ^{\?}\?\?^{\?}\?\?, Amer. Math. Monthly 108 (2001), no. 2, 151 – 154. · Zbl 1005.26008 · doi:10.2307/2695528
[28] 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. · Zbl 1163.13021 · doi:10.1007/978-0-387-09686-5_7
[29] Jim Lawrence, Polytope volume computation, Math. Comp. 57 (1991), no. 195, 259 – 271. · Zbl 0734.52009
[30] Shaowei Lin, Bernd Sturmfels, and Zhiqiang Xu, Marginal likelihood integrals for mixtures of independence models, J. Mach. Learn. Res. 10 (2009), 1611 – 1631. · Zbl 1235.62009
[31] 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. · Zbl 0878.65010 · doi:10.1007/3-540-60114-7_27
[32] 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. · Zbl 0864.65008
[33] T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math. 17 (1965), 533 – 540. · Zbl 0129.39902 · doi:10.4153/CJM-1965-053-6
[34] Luis Rademacher, Approximating the centroid is hard, Computational geometry (SCG’07), ACM, New York, 2007, pp. 302 – 305. · Zbl 1221.68095 · doi:10.1145/1247069.1247123
[35] Murray Schechter, Integration over a polyhedron: an application of the Fourier-Motzkin elimination method, Amer. Math. Monthly 105 (1998), no. 3, 246 – 251. · Zbl 0929.15018 · doi:10.2307/2589079
[36] Z. Xu, Multivariate splines and polytopes, arXiv: 0806.1127v3, 2009. · Zbl 1275.41015
[37] Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. · Zbl 0823.52002
[38] O. C. Zienkiewicz and R. L. Taylor, The finite element method, McGraw-Hill, London, 1988. · Zbl 0991.74002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.