3
$\begingroup$

We've been preparing a preprint that shows that the convergence bounds proved for tanh-sinh quadrature for numerical integration, cannot possibly hold, and an error must exist - since they imply a P time algorithm to a #P problem. The preprint can be accessed at https://github.com/naturalog/prodcos/blob/master/prodcos.pdf

Maybe someone here have any idea about what is going on here?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Have you checked this on the trapezoidal rule as well? It's also exponentially convergent for periodic functions such as yours, and the error bounds are much easier to derive explicitly. $\endgroup$
    – Kirill
    Commented Dec 28, 2015 at 0:12
  • $\begingroup$ Indeed, just finished writing a proof for that :) Just uploaded updated pdf to github. It's all still preliminary though. $\endgroup$
    – Ohad Asor
    Commented Dec 28, 2015 at 0:32
  • 1
    $\begingroup$ For trapezoidal rule, for $f(t) = \prod_k \cos x_k t$, the usual Fourier analysis would suggest you need to sample the function on at least $\approx \sum_k|x_k|$ points (which I think would be exponentially large in your case) to get an estimate accurate to $2^{-n}$, which is why I thought it might be a counterexample. Even in the DE formula, intuitively it seems you need $O(|x|)$ points to resolve the integrand's oscillations, rather than $O(n)$ points, similar to the trapezoidal rule. $\endgroup$
    – Kirill
    Commented Dec 28, 2015 at 0:59
  • $\begingroup$ Right, the Fourier analysis would suggest points that'll keep it outside of P, as can be seen by translating the product of n cosines into sum of 2^n cosines. This is definitely part of why it is all so confusing. But the paper suggests a calculation for the number of points needed, including the precision needed, and it all seems P. $\endgroup$
    – Ohad Asor
    Commented Dec 28, 2015 at 1:03
  • $\begingroup$ I think the error is, as Brendan McKay pointed out, that the convergence depends on the integrand. Compare (visually) convergence of the DE rule for $\int_{-1}^{1} \cos \pi t\,dt$ and $\int_{-1}^{1}\cos 10\pi t\,dt$. Even if the constant $c$ in $O(e^{-c N})$ is independent of the integrand $f$ under some assumptions on $f$, there is yet another constant in the $O$ that does depend on $f$. Indeed, it seems outright impossible that there is a way to evaluate $\int_{-1}^{1}\cos \pi x t\,dt$ in $O(1)$ function evaluations, independent of $x$. $\endgroup$
    – Kirill
    Commented Dec 28, 2015 at 1:53

1 Answer 1

Reset to default
9
$\begingroup$

I don't know the solution, but the thing that most bothers me about your preprint is the non-explicit nature of Theorem 2 and your inferences from it. Each $O(\,)$ has some "constant" implied in it, but what do the "constants" depend on? Theorem 2 as you state it suggests to me that the "constants" may depend on $f$, which potentially kills your argument. To make your case convincing you need a form of Theorem 2 where each $O(\,)$ is replaced by an explicit bound on the quantity that is being estimated.

Answering first comment: I don't think the bound can possibly be independent of $f$. For given $N$ we can modify $f$ any way we like except at the $2N+1$ points we are evaluating it at. I don't believe all such modifications have the same integral within the given error; why should they? Second, looking back at the definition of $H^2$, I also suspect that the integral error depends on the actual value of the sup and not just on whether it is finite or infinite. Third, another way that the bound can depend on $f$ is that the "for large enough $N$" implicit in the $O(\,)$ notation can depend on $f$.

Further comments: (A) I cannot find [5] in "Mathematics of Computation" or any other journal. If that is true, I suggest you communicate with the authors as to why their paper did not appear. (B) The presence of $O(\,)$ expressions in Thm 2 is still enough to doubt your claims. You need to bound every quantity with an explicit formula. (C) The number of function evaluations is not enough. You have to consider the cost of very high precision evaluation of the transform.

Improve this answer
$\endgroup$
4
  • $\begingroup$ right, and indeed, the constant are independent of the integrand, as stated in the Borwein&Ye paper where the theorem was taken from. will make it clear. thanks! $\endgroup$
    – Ohad Asor
    Commented Dec 26, 2015 at 8:11
  • $\begingroup$ after your edit: yes, indeed, disturbing questions - and indeed we claim that the quadrature rates are too optimistic. alas, they are proved both theoretically and experimentally. we can't point to an error yet. $\endgroup$
    – Ohad Asor
    Commented Dec 26, 2015 at 8:35
  • $\begingroup$ thanks, all your comments will be taken into account in the new revision that will be published tomorrow. We do think we can show that the result still holds, even in more general cases. In fact we derived a new proof without O() at all. $\endgroup$
    – Ohad Asor
    Commented Dec 27, 2015 at 23:17
  • $\begingroup$ we have uploaded a new version (in the above github link) and will go to arxiv soon. we have paid a lot of attention to your remarks and in fact we do not rely on the firstly mentioned results but on numerous other results that were published in peer-reviewed papers. we also did not forget to acknowledge you in the paper. thanks again! $\endgroup$
    – Ohad Asor
    Commented Jan 2, 2016 at 1:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .