# Advice on numerical integration of a very "sparse" function

**URL:** <https://discourse.julialang.org/t/advice-on-numerical-integration-of-a-very-sparse-function/18176>\
**Category:** Numerics\
**Tags:** question\
**Created:** [November 30, 2018, 10:00am UTC](https://discourse.julialang.org/t/advice-on-numerical-integration-of-a-very-sparse-function/18176 "2018-11-30T10:00:55Z")\
**Posts on this page:** 6\
**Page:** 2

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [November 30, 2018, 2:11pm UTC](https://discourse.julialang.org/t/advice-on-numerical-integration-of-a-very-sparse-function/18176/21 "2018-11-30T14:11:19Z")

</div>

That is the case for every possible method that has only oracle access and no bounds.

You either need to do away with the oracle model (e.g. interval arithmetic) or need to provide explicit bounds. For example, bounds could look like: Each evaluation gives you `f(x)`, `L=L(x)` and `r=r(x)>0` such that the function is L-Lipschitz in the ball `B_r(x)`. Then you are guaranteed an approximation on compact domains in finitely many oracle calls. Note that AD can give speedups but cannot help you jump from “undecidable problem” to “decidable”.

Unqualified smoothness without explicit estimates is meaningless in most contexts (polynomials are dense; not even analyticity can help you!).

Edit: Lipschitz is overkill. You need access to the modulus of absolute continuity in a small but finite compact neighborhood. Local Hoelder is totally fine as an alternative.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [November 30, 2018, 2:16pm UTC](https://discourse.julialang.org/t/advice-on-numerical-integration-of-a-very-sparse-function/18176/22 "2018-11-30T14:16:14Z")

</div>

> [@foobar\_lv2](#):
>
> Note that AD can give speedups but cannot help you jump from “undecidable problem” to “decidable”.

Not sure about this; if the domain is smooth and otherwise connected (zeros are only numerical, not truly 0, and I can transform to logs for better calculations), I would try Hamiltonian Monte Carlo if I have AD.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [November 30, 2018, 2:21pm UTC](https://discourse.julialang.org/t/advice-on-numerical-integration-of-a-very-sparse-function/18176/23 "2018-11-30T14:21:15Z")

</div>

Sure you can do heuristics. But my point is the following:

You are given oracle access to a polynomial `P` on the interval `[0,1]`. You want to output one of:

1. `P` is large: There exists at least one point with `P(x)>1`.
2. `P` is small: All points have `P(x)<2`.

Without additional information, this problem is undecidable. Simply because I can trace all evals of your algorithm and use polynomial interpolation to find an example where your algorithm fails. If you do AD, then I also fix the derivatives you evaluated.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [November 30, 2018, 2:46pm UTC](https://discourse.julialang.org/t/advice-on-numerical-integration-of-a-very-sparse-function/18176/24 "2018-11-30T14:46:00Z")

</div>

Of course you are right in the mathematical sense, but in a practical problem one hopes that the function isn’t that bad. In any case, I think the original example has 2 modes, which should be manageable with heuristics.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [November 30, 2018, 2:50pm UTC](https://discourse.julialang.org/t/advice-on-numerical-integration-of-a-very-sparse-function/18176/25 "2018-11-30T14:50:25Z")

</div>

> [@stevengj](#):
>
> We can add some keyword argument to force HCubature to subdivide the domain at the beginning to ensure that it is sampled more finely to start with.

The master branch now has an `initdiv` option that should address this.

---

<div class="post-metadata">

**Author:** ![yakir12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yakir12/32/297_2.png) [@yakir12](https://discourse.julialang.org/u/yakir12)\
**Post date:** [November 30, 2018, 2:59pm UTC](https://discourse.julialang.org/t/advice-on-numerical-integration-of-a-very-sparse-function/18176/26 "2018-11-30T14:59:46Z")

</div>

> [@stevengj](#):
>
> an `initdiv` option that should address this

I can confirm that indeed it does 🙂

[Previous page](https://discourse.julialang.org/t/advice-on-numerical-integration-of-a-very-sparse-function/18176.md?page=1)