numerical integration in many variables

Question

Let $\vec{x} = (x_1, x_2, \dots, x_n) \in [0,1]^n$ and $f(\vec{x}): [0,1]^n \to \mathbb{C}$ be a function in these variables.

Is there a recursive scheme for this iterated integral?

$$\int_{[0,1]^n} \prod dx_i \;f(\vec{x}) $$

If $n = 10$ and I break $[0,1]$ into 100 segments, we have $10^{20}$ points to add up. There must be a smarter way.

---

In fact, the function I wish to integrate is the Haar measure of the Unitary group.

$$\int_{U(n)} f(A) \ dA = \frac{1}{n!} \int_{[0,2\pi]^n} \prod_{j<k} \big|e^{i \theta_j} - e^{i \theta_k}\big|^2 \cdot f(\theta_1, \ldots, \theta_n) \ \frac{d \theta_1}{2\pi} \ \cdots \ \frac{d \theta_n}{2\pi}$$

Answer 1

For integrations with many variables, the Monte Carlo method usually is a decent fit. Its error decreases as $O (\sqrt{N})$ where N is the number of equidistributed points selected. Of course this is not good for low dimension (1D and 2D) spaces where high order methods exist. Most of these deterministic methods, however, take a large number of points in higher dimensions. For example, a 1st order 1D scheme is $O(\sqrt{N})$ in 2D and $O(N^{\frac{1}{4}})$ in 3D. The strength of the Monte Carlo method is that the error convergence is independent of space dimension. No matter whether your space is 1D or 100D, it is $O (\sqrt{N})$.

Since it is probabilistic, however, you need to integrate it multiple times using a set number of points to find a standard deviation and an estimate of your error.

Answer 2

Sparse grid quadrature is an alternative approach to integrate in higher dimensions.

Quadrature relies on evaluating a weighted sum of function values at specific "optimal" points. Traditional quadrature uses a tensor product grid construction in higher dimensions, which means that you would have to evaluate the function at an exponentially growing number of points as the dimension increases.

The trick to sparse grid quadrature is that you can obtain the same order accuracy (in the asymptotic sense) using a small subset of the tensor product grid. The sparse points you choose end up being those that accurately integrate monomials of up to a desired total degree. The computational savings (compared to the tensor product grid) increase significantly as the dimension increases.

There are, however, drawbacks to this method that you should be aware.

1. This method does not work well if your function is not smooth (or otherwise not well approximated by polynomial functions).
2. While the order of accuracy of sparse grid quadrature may be equivalent to a tensor product grid, the relative accuracy may be much worse. This is because the constant in front of the sparse grid's order of accuracy can be very large.
3. Sparse grids work well for relatively small dimensions. But there comes a dimension after which you'd probably be better off using another method (like monte carlo or its variants).

For more information on sparse grids, I recommend Burkardt's Sparse Grids in High Dimensions. If you're interested in code to generate sparse grids, you may want to consider these matlab files.