Timeline for What is the computational complexity to compute the integral numerically?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2014 at 6:27 | comment | added | XL _At_Here_There | Actually, I have been suspecting that there exists a polynomial time complexity algorithm, but one paper Steve give in the comment has claims that the computational complexity is $NP-$hard. I have to carefully read the article or think about the question again. | |
| Nov 22, 2014 at 6:13 | comment | added | XL _At_Here_There | @BrunoLeFloch, thank you for your comments. I am wondering whether the antiderivative of the integrand is relevant to the complexity. In fact, your suspicion may be relating the kind of anti-derivative. | |
| Nov 22, 2014 at 6:05 | comment | added | XL _At_Here_There | @SteveHuntsman, thank you for the reference. | |
| Nov 22, 2014 at 5:58 | comment | added | Bruno Le Floch | 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. | |
| Nov 22, 2014 at 5:53 | comment | added | Steve Huntsman | dx.doi.org/10.1007/s00211-009-0284-9 | |
| Nov 22, 2014 at 5:45 | comment | added | Steve Huntsman | arxiv.org/abs/0809.2083 | |
| Nov 22, 2014 at 5:09 | comment | added | Bruno Le Floch | Even in the one variable case, I suspect that this strongly depends on whether the roots of $P_2$ lie close to $\Delta$. | |
| Nov 22, 2014 at 4:47 | history | asked | XL _At_Here_There | CC BY-SA 3.0 |