# numerical integral vs counting roots

I have a problem that can be viewed in two different ways:

1. Compute an $n$-dimensional integral, numerical context. The domain of integration is an $n$-dimensional hyper-cube of side $L$.

2. Count (just count) the roots of an $n$-dimensional function (not a polynomial).

Solving just one of them is sufficient for solving the original problem. I know that simple algorithms for numerical integration would take $O(L^n)$, taking linear time per dimension. But I am not sure if there an asymptotically faster algorithms for (1).

For (2), I am aware of algorithms that can find roots (Newton and Bisection), but I am not sure about the best algorithms just for counting how many roots are in a non-polynomial $n$-dimensional function.

What are the best algorithms for (2)? Are they better than the fastest of (1)?

• Not an expert, but "Best" would probably depend on your specific situation... Apr 8 '13 at 22:35
• Details on the function would certainly help. Can you factor it? Do a substitution that groups variables (that way leaving out some)? How do you know there are isolated roots, not hyperplanes on which the function vanishes? Apr 9 '13 at 10:09
• @Aryabhata could be. Anyway, the only parameter as input is $n$ ($L$ grows linearly as $O(n)$). Apr 9 '13 at 14:19
• @vonbrand: Unfortunately we cannot factor it. For substitution intuition says no but we will check this aspect more in detail. The roots are isolated, even when the domain is continuous, the roots fall just fall in discrete places. Thanks. Apr 9 '13 at 14:27