7
$\begingroup$

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)?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Not an expert, but "Best" would probably depend on your specific situation... $\endgroup$
    – Aryabhata
    Commented Apr 8, 2013 at 22:35
  • 1
    $\begingroup$ 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? $\endgroup$
    – vonbrand
    Commented Apr 9, 2013 at 10:09
  • $\begingroup$ @Aryabhata could be. Anyway, the only parameter as input is $n$ ($L$ grows linearly as $O(n)$). $\endgroup$
    – labotsirc
    Commented Apr 9, 2013 at 14:19
  • $\begingroup$ @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. $\endgroup$
    – labotsirc
    Commented Apr 9, 2013 at 14:27

2 Answers 2

Reset to default
1
$\begingroup$

Consider using Monte Carlo method for computing quadrature. It is good choice when you need not so precise approximation and dimension of the domain is large.

You definitely should provide more details.

Improve this answer
$\endgroup$
0
$\begingroup$

If you view the evaluation of your function at tensor-product quadrature points in the cube, then the resulting box of numbers forms a tensor. If there is some low rank underlying structure to this tensor, you could use some of the new tensor-train approximation techniques to approximate the tensor while evaluating the tensor at many fewer quadrature points. See the work of Ivan Osledets on tensor trains, in particular TT-cross which is based off the skeleton matrix decomposition for the different matricizations of the tensor.

http://www.mat.uniroma2.it/~tvmsscho/papers/Tyrtyshnikov5.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.