2
$\begingroup$

Given $$\int_{\Delta}\frac{P_1(x_1,x_2,\dots,x_n)}{P_2(x_1,x_2,\dots,x_n)}$$ where $P_i$ is polynomial(that is $P_1(x_1,x_2,\dots,x_n), P_2(x_1,x_2,\dots,x_n)$ are polynomial) whose coefficients are over $\mathbb{Q}$,$\Delta$ is the domain defined by polynomial inequality with coefficients over $\mathbb{Q}$,What is the computational complexity to compute the integral numerically? Especialy in the term of polynomials and the polynomials inequality defining the domain.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Even in the one variable case, I suspect that this strongly depends on whether the roots of $P_2$ lie close to $\Delta$. $\endgroup$
    – Bruno Le Floch
    Commented Nov 22, 2014 at 5:09
  • 1
    $\begingroup$ arxiv.org/abs/0809.2083 $\endgroup$
    – Steve Huntsman
    Commented Nov 22, 2014 at 5:45
  • 2
    $\begingroup$ dx.doi.org/10.1007/s00211-009-0284-9 $\endgroup$
    – Steve Huntsman
    Commented Nov 22, 2014 at 5:53
  • 3
    $\begingroup$ Crucially, the first paper cited by @SteveHuntsman, "How to integrate a polynomial over a simplex" by Baldoni, Berline, De Loera, Köppe and Vergne focuses on polynomials. For rational functions, we end up having to approximate $\log$ or $\arctan$ and don't only get rational numbers. An instructive example could be $\int_0^1 P(x) / (x + 1) \mathrm{d}x = a \log 2 + b$. The rational numbers $a$ and $b$ are cheap to compute from the coefficients of $P$, but if $-b/a\simeq\log 2$ only a specifically Taylored algorithm would approximate $a\log 2 + b$ efficiently. $\endgroup$
    – Bruno Le Floch
    Commented Nov 22, 2014 at 5:58
  • $\begingroup$ @SteveHuntsman, thank you for the reference. $\endgroup$
    – XL _At_Here_There
    Commented Nov 22, 2014 at 6:05

0

Reset to default

You must log in to answer this question.