PaperlayerView exact revision on arXiv

Source-linked AI summary

How to Integrate a Polynomial over a Simplex

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

arXiv:0809.2083v3math.MGcs.CCcs.SC

TL;DR

The paper asks how efficiently exact polynomial integrals over rational simplices can be computed. It proves hardness for arbitrary polynomials and gives polynomial-time algorithms for fixed-variable and fixed-degree cases.

  • Problem

    The paper examines the computational complexity of exactly integrating a rational-coefficient polynomial over a rational simplex.

    Source: §1 · p. 1

  • Method

    It proves hardness using powers of the Motzkin–Straus quadratic form and establishes tractable cases through monomial variable counts and decompositions into powers of linear forms.

    Source: §1 · pp. 3–4

  • Results

    General polynomial integration is NP-hard, while integration is polynomial-time when the number of variables is fixed or the total degree is fixed.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The results distinguish hard general inputs from fixed-variable and fixed-degree cases that admit polynomial-time integration.

    Source: §1 · pp. 3–4

    The input representation excludes general straight-line programs, which are too compact for the paper’s purposes, and instead restricts to SIU programs.

    Source: §1 · p. 2

Abstract

from arXiv · show

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.

1. Introduction

The paper studies exact integration of rational-coefficient polynomials over rational simplices, establishing hardness for general polynomials and polynomial-time algorithms under fixed-variable or fixed-degree conditions. It also motivates the problem through applications and describes methods for the tractable cases.

1. Introduction

  • The paper uses integral Lebesgue measure on the simplex’s rational affine hull, making polynomial integrals rational; induced Euclidean measure can yield irrationals.The normalization also occurs naturally in Euler–Maclaurin formulas.Source: §1 · p. 1
  • Polynomial integrals arise in lattice-point sums, moment-matrix optimization, finite-element methods, random-polynomial zero counts, and statistics.Simplices are a fundamental integration case because convex polytopes can be triangulated into simplices.Source: §1 · pp. 1–2
  • Exact integration over a rational simplex is NP-hard for general polynomials represented by SIU straight-line programs.The theorem takes unary dimension parameters, binary rational vertices, and outputs the integral in binary.Source: §1 · p. 3
  • When the polynomial depends on a fixed number of linear forms, integration is polynomial-time even as degree and simplex dimension vary.The input specifies the forms through a rational matrix with a fixed number of rows.Source: §1 · p. 3
  • The hardness proof uses powers of the Motzkin–Straus quadratic form, while the positive results use monomial variable counts and decompositions into powers of linear forms.A polarized multilinear-form formula also yields a proof of the fixed-degree result.Source: §1 · pp. 3–4
  • For every fixed total degree, polynomial integration over a rational simplex also has a polynomial-time algorithm.The result applies to SIU, sparse, or dense polynomial representations.Source: §1 · p. 4

2. Preliminaries

The preliminaries establish the measure used for simplex integration, explain polynomial encodings suited to the computational model, and provide an algorithm for truncated products in a fixed number of variables.

2.1. Integral Lebesgue measure on a rational affine subspace of Rn.

  • The integral Lebesgue measure on a rational affine subspace is normalized so the fundamental domain of its intersected lattice has volume 1.The diagonal of the unit square consequently has length 1 under this measure.Source: §2.1 · pp. 4–5

2.2. Encoding polynomials for integration.

  • Straight-line programs encode polynomials as sequences of additions and multiplications, sometimes using polynomial space where monomial representations require exponentially many terms.Their formal degree is defined recursively, and bounds the polynomial's total degree.Source: §2.2 · pp. 5–6
  • Compact straight-line encodings can make exact outputs exponentially larger than their inputs, motivating SIU programs in which each intermediate result is used only once.For x^(2k), the SIU restriction requires at least 2k multiplications and is equivalent in expressiveness and encoding complexity to fully parenthesized expressions using + and ×.Source: §2.2 · pp. 6–7

2.3. Efficient computation of truncated product of an arbitrary number of polynomials in a fixed number of variables.

  • For fixed D, multiplying k dense polynomials in D variables and truncating at degree M can be done in polynomial time.The algorithm uses O(kM^(2D)) rational operations when M is given in unary.Source: §2.3 · pp. 7–8

3. Proofs of the main results

The proofs establish hardness for polynomial integration when degree varies and polynomial-time algorithms under fixed-variable or fixed-degree restrictions, using graph-clique hardness and integration formulas for products of powers of linear forms. For fixed-degree polynomials, they also present an alternative algorithm and a special-case test for powers of a linear form that avoids unnecessary decomposition.

3.1. Hardness for polynomials of non-fixed degree.

  • Integrating arbitrary-degree polynomials over simplices is NP-hard via a reduction from deciding whether a graph’s clique number exceeds a given threshold.The reduction uses a sufficiently high power of the Motzkin–Straus quadratic form; its straight-line program has length O(n^3 log n · |E(G)|).Source: §3.1 · p. 10

3.2. An extension of a formula of Brion.

  • The paper extends Brion’s formula to Taylor expansions for products of powers of linear forms, yielding formulas used in the fixed-variable algorithm.For one regular linear form, the expansion recovers Brion’s short formula.Source: §3.2 · pp. 11–12

3.3. Polynomial time algorithm for polynomial functions of a fixed number of linear forms.

  • For fixed D, the integral of f(⟨ℓ1,x⟩,…,⟨ℓD,x⟩) over a simplex can be computed in polynomial time in the input data.The algorithm uses Corollary 11 to compute the integrals of monomials in the D linear forms.Source: §3.3 · p. 14

3.4. Polynomial time algorithms for polynomials of fixed degree.

  • For fixed total degree, integration is polynomial-time because each monomial depends on at most M coordinates and can use the fixed-linear-form algorithm.The section also gives an alternative efficient algorithm based on decomposing polynomials into sums of powers of linear forms.Source: §3.4 · p. 15
  • Formula (13) and Corollary 13 yield another polynomial-time algorithm for integrating fixed-degree polynomials, implemented in the Maple program waring.mpl.The implementation is referenced in Tables 6 and 10.Source: §3.4 · p. 16
  • For fixed degree, one can decide in polynomial time whether a polynomial in sparse or dense monomial representation is a power of a linear form and construct that form if it is.This special case avoids applying the decomposition formula separately to each monomial of the polynomial.Source: §3.4 · p. 17

4. Other algorithms for integration and extensions to other polytopes

The section reviews alternative integration formulas, traditional iterated integration, and extensions from simplices to other polytopes. Some methods yield polynomial-time algorithms in restricted settings, while others face exponential complexity or hard triangulation problems.

4.1. A formula of Lasserre–Avrachenkov.

  • The section also presents the Lasserre–Avrachenkov formula as an alternative proof of the fixed-degree result, using a polarization formula for homogeneous polynomials.A homogeneous polynomial can be represented through a multilinear form, which can be computed using a decomposition into powers of linear forms or polarization.Source: §4.1 · pp. 17–18
  • For fixed degree, the Lasserre–Avrachenkov formula gives another polynomial-time algorithm for integration over a simplex in varying dimension.With the degree fixed, the polarization formula has constant length, and the first sum has polynomial length.Source: §4.1 · pp. 17–18

4.2. Traditional conversion of the integral as iterated univariate integrals.

  • Fourier–Motzkin elimination generates iterated integral bounds, but its inequalities and resulting summands can grow exponentially as dimension varies.The method projects away variables to produce bounds for one-dimensional integrals; repeated elimination can cause exponential growth.Source: §4.2 · pp. 18–20

4.3. Two formulas for integral computation.

  • Facet-based and vertex-based formulas yield polynomial-time integration for two specified polytope representations, but facet reduction can leave many complicated facets.The two cases are simplicial polytopes given by facet inequalities and simple polytopes given by vertices.Source: §4.3 · pp. 20–21

4.4. Triangulation of arbitrary polytopes.

  • Triangulation extends simplex integration to convex polytopes, but its cost depends on the number of simplices, and finding a smallest triangulation is NP-hard even in dimension three.For nonconvex polyhedra, triangulation may require adding points, and deciding how many are necessary is NP-hard.Source: §4.4 · pp. 21–22

5. Implementation and computational experiments

The authors report initial Maple experiments with the three methods described in Section 3.4.

5. Implementation and computational experiments

  • Maple programs were used for initial experiments with the three methods described in Section 3.4, and the programs are available at.Source: §5 · p. 22

5.1. Integration of a power of a linear form and decomposition of polynomials into powers of linear forms.

This section reports computational experiments on decomposing polynomials into powers of linear forms and integrating those forms and random monomials over simplices.

5.1.1. Decomposition of polynomials into powers of linear forms.

  • Table 4 reports F(n, M), the number of primitive linear forms that may appear in a degree-at-most-M polynomial decomposition, computed by formula (14).The table concerns decompositions of polynomials into powers of linear forms.Source: §5.1.1 · p. 22, Table 4 · p. 22

5.1.2. Integration of a power of a linear form over a simplex.

  • A Maple program implements the method for integrating a power of one linear form over a simplex.The implementation is described as using Corollary 13.Source: §5.1.1 · p. 23
  • The power-of-a-linear-form experiment used random full-dimensional simplices and random linear forms for each chosen dimension n and degree M.Table 5 presents computation times; experiments used Maple 12 on 1.6 GHz UltraSPARC-IIIi processors and had a 600-second per-example limit.Source: §5.1.2 · p. 23, Table 5 · p. 23, §5.1.3 · p. 23

5.1.3. Integration of a monomial over a simplex by decomposition as sum of powers of linear forms.

  • For monomial integration by decomposition, the experiment sampled 50 random simplex–exponent-vector combinations for each dimension n and total degree M.Each monomial was decomposed into powers of linear forms, and each summand was integrated with the linear-form procedure; Table 6 reports minimum, average, and maximum computation times.Source: §5.1.3 · p. 23, Table 6 · p. 24
  • The reported experiments used Maple 12 on Sun Fire V440 machines with UltraSPARC-IIIi processors running at 1.6 GHz, with a 600-second limit per example.Times are reported in CPU seconds.Source: §5.1.3 · p. 23
  • The monomial-decomposition implementation is the Maple procedure integral via waring in waring.mpl.The linear-form integration procedure is integral_power_linear_form in waring.mpl.Source: §5.1.3 · p. 23

5.2. Integration of a monomial, using iterated Laurent series.

This section tests the iterated Laurent expansion method for integrating monomials over a simplex. The reported results are in Table 7.

5.2. Integration of a monomial, using iterated Laurent series.

  • Table 7 reports results for the implementation of the iterated Laurent expansion method on monomial integration.The method is described in Remark 15 of Section 3.4.Source: §5.2 · p. 25, Table 7 · p. 25
  • The implementation is provided as the Maple procedure integral via iterated in iterated_laurent.mpl.The table is captioned as covering random monomials of prescribed degree.Source: §5.2 · p. 25, Table 7 · p. 25

5.3. Integration of a monomial, using Taylor expansion.

This section tests the algorithm based on Corollary 11 for integrating monomials over a simplex. Table 8 presents the running times.

5.3. Integration of a monomial, using Taylor expansion.

  • Table 8 reports running times for the tested monomial-integration algorithm based on Corollary 11.The table is captioned as covering random monomials of prescribed degree.Source: §5.3 · p. 26, Table 8 · p. 26
  • The implementation is the Maple procedure integral via duality in duality.mpl.The paper also identifies a formula for integrating a product of powers of several linear forms.Source: §5.3 · p. 26

5.4. Integration of a dense homogeneous polynomial over a simplex.

The experiments test three methods on randomly generated, very dense homogeneous polynomials, and the paper reports results in Tables 10–12.

5.4. Integration of a dense homogeneous polynomial over a simplex.

  • The random polynomial generator requested r monomials of homogeneous degree M, with exponent vectors drawn uniformly among degree-M vectors and coefficients drawn uniformly from 1 to 100.Collisions could leave the generated polynomial with fewer than r monomials.Source: §5.4 · p. 27
  • The tested polynomials were randomly generated, very dense homogeneous polynomials, and Tables 10–12 report results for the three methods.Table 9 reports the number of monomials in the resulting polynomials.Source: §5.4 · p. 27
  • For the decomposition method, coefficients of linear-form powers shared by multiple monomial decompositions were collected.The same powers can occur in decompositions of different monomials.Source: §5.4 · p. 27

5.5. Integration of a monomial with few effective variables.

The experiments compare three integration methods on monomials with few effective variables, reporting tables for the two-variable case. They also provide dense-polynomial tables for each method.

5.5. Integration of a monomial with few effective variables.

  • The few-effective-variable monomial experiment samples 50 random simplex and exponent-vector combinations for fixed D, and reports results only for D = 2.The tested exponent vectors have D potentially nonzero entries and total degree M.Source: §5.5 · p. 27
  • Separate tables cover random dense homogeneous polynomials of prescribed degree using each of the three integration methods.A further table counts monomials in the test family of random dense homogeneous polynomials.Source: Table 9 · p. 28, Table 10 · p. 29, Table 11 · p. 30
  • For monomials with 2 effective variables, the tables report integration by linear-form decomposition, iterated Laurent expansion, and Taylor expansion.The tables concern monomials of prescribed degree.Source: Table 13 · p. 32, Table 14 · p. 33, Table 15 · p. 34

5.6. Discussion.

The experiments rank the three methods differently by dimension: iterated Laurent expansion leads at small dimensions, while linear-form decomposition leads from dimension six. Few effective variables benefit all methods, but Taylor expansion remains behind the better alternative.

5.6. Discussion.

  • From dimension n = 6, decomposition into powers of linear forms is faster than the other methods; up to n = 5, iterated Laurent expansion is faster.Taylor expansion is always inferior to whichever of those methods is faster.Source: §5.6 · p. 35
  • For random dense polynomials, collecting coefficients of identical linear-form powers yielded no significant savings, and the method ranking matched the random-monomial case.The reported ranking is therefore iterated Laurent expansion for n ≤ 5 and linear-form decomposition from n = 6.Source: §5.6 · p. 35
  • Few effective variables benefit all three methods, with the largest effect on linear-form decomposition, which handles degree M = 200 and dimension n = 15 at D = 2.At n ≤ 5, iterated Laurent expansion still wins; Taylor expansion remains inferior to the better method.Source: §5.6 · p. 35

6. Conclusions

The paper discusses exact-integration algorithms for simplicial regions and reports that rough experiments found them robust on difficult problems. It also identifies theoretical and practical directions for further work.

6. Conclusions

  • The authors conclude that their exact-integration algorithms are theoretically efficient and that rough experiments found them robust on difficult problems.The paper's experiments are described as simple and rough.Source: §6 · p. 36
  • Future theoretical work includes possible inapproximability results for the hardness theorem and efficient integration for other polytope families.The authors also plan efficient computation of highest-degree coefficients of weighted Ehrhart quasipolynomials of simplices.Source: §6 · p. 36
  • Practical integration software may need to pair these methods with fast domain decomposition, such as triangulation.Source: §6 · p. 36
Loading 0809.2083v3…