How to integrate a polynomial over a simplex
From MaRDI portal
Abstract: This paper settles 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 conclude the article with extensions to other polytopes, discussion of other available methods and experimental results.
Recommendations
- Integration of polynomials over \(n\)-dimensional polyhedra
- Efficient integration over polytopes
- Simple formula for integration of polynomials on a simplex
- scientific article; zbMATH DE number 4110107
- Multivariate polynomial integration and differentiation are polynomial time inapproximable unless \(\text{P}=\text{NP}\)
Cites work
- scientific article; zbMATH DE number 431987 (Why is no real title available?)
- scientific article; zbMATH DE number 52134 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 735289 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1057758 (Why is no real title available?)
- scientific article; zbMATH DE number 3996785 (Why is no real title available?)
- scientific article; zbMATH DE number 773851 (Why is no real title available?)
- A geometric inequality and the complexity of computing volume
- Algorithm 824
- An adaptive numerical cubature algorithm for simplices
- Approximating the centroid is hard
- Computation of exponential integrals
- Counting linear extensions
- Exponential sums and integrals over convex polytopes
- Finite element method. Vol. 1: The basis.
- Integration on a convex polytope
- Integration over a Polyhedron: An Application of the Fourier-Motzkin Elimination Method
- Invariant Integration Formulas for the n-Simplex by Combinatorial Methods
- Lattice points in simple polytopes
- Lectures on Polytopes
- Local Euler-Maclaurin formula for polytopes
- Marginal likelihood integrals for mixtures of independence models
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Multivariate splines and polytopes
- On Multivariate B-Splines
- On the Alexander-Hirschowitz theorem
- On the Complexity of Computing the Volume of a Polyhedron
- Points entiers dans les polyèdres convexes
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Polytope Volume Computation
- Sums of squares, moment matrices and optimization over polynomials
- Symmetric tensor decomposition
- The Multi-Dimensional Version of � b a x p dx
- Triangulations. Structures for algorithms and applications
Cited in
(48)- Dense classes of multivariate extreme value distributions
- Gaining or losing perspective for convex multivariate functions on box domains
- Computing sieve integrals using LattE, and the density of integers with a localized divisor
- Exploiting symmetries in polyhedral computations
- Computations of volumes and Ehrhart series in four candidates elections
- Integration and optimization of multivariate polynomials by restriction onto a random subspace
- Exploiting polyhedral symmetries in social choice
- Polyhedral star-shaped distributions
- Numerical reconstruction of convex polytopes from directional moments
- Integration over facet-simple polytopes
- Nearly optimal simple explicit MPC controllers with stability and feasibility guarantees
- Numerical integration of homogeneous functions on convex and nonconvex polygons and polyhedra
- The inverse moment problem for convex polytopes
- Moment varieties of measures on polytopes
- Symmetric tensor decomposition
- Three Ehrhart quasi-polynomials
- Numerical integration of polynomials and discontinuous functions on irregular convex polygons and polyhedrons
- On the score sheets of a round-robin football tournament
- Simple formula for integration of polynomials on a simplex
- On fundamental domains and volumes of hyperbolic Coxeter-Weyl groups
- Multi-collinear splitting kernels for track function evolution
- Minimizing rational functions: a hierarchy of approximations via pushforward measures
- Intermediate sums on polyhedra: computation and real Ehrhart theory
- Integrating products of quadratic forms
- A new recursive formula for integration of polynomial over simplex
- Average weights and power in weighted voting games
- Extension of the Lasserre-Avrachenkov theorem on the integral of multilinear forms over simplices
- Combinatorial excess intersection
- The computation of generalized Ehrhart series in normaliz
- Computing asymptotic bounds for small roots in Coppersmith's method via sumset theory
- Weighted Ehrhart functions
- Optimization on the Euclidean unit sphere
- Sampling and change of measure for Monte Carlo integration on simplices
- Strange expectations and simultaneous cores
- Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
- A family of explicit Waring decompositions of a polynomial
- Weighted Ehrhart theory: extending Stanley's nonnegativity theorem
- On moments of a polytope
- Advanced SMT techniques for weighted model integration
- Polyhedral omega: a new algorithm for solving linear Diophantine systems
- The best ways to slice a polytope
- Volume of slices and sections of the simplex in closed form
- scientific article; zbMATH DE number 4110107 (Why is no real title available?)
- Stable parameterization of continuous and piecewise-linear functions
- Learning probabilistic logic programs over continuous data
- Multivariate polynomial integration and differentiation are polynomial time inapproximable unless \(\text{P}=\text{NP}\)
- Multiplicities of classical varieties
- Sums of weighted lattice points of polytopes
Describes a project that uses
Uses Software
This page was built for publication: How to integrate a polynomial over a simplex
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3081285)
