# Working with multi-dimensional functions

How would you represent functions of type $[-1, 1]^n \to \mathbb R \;$ for moderate $n$? How would you integrate them?

For small $n$ (1-2) such functions can be represented as histograms, vectors in some base, etc. For really large $n$ one employs other techniques, like neural networks or for integration monte-carlo methods. But what if I have to deal with $n= \overline{6 \ldots 12} \;$ ? I need to be able to compute such functions (for later integration to $\mathbb R$), but how to store, how to represent them?

Having 100 points for each dimension will lead to $100^6 = 10^{12}$, whereas GiB is around $10^9$ bytes.

• It's a little unclear; you want to numerically integrate a sampled real-valued function? Do you have access to an analytic expression? How did the samples originate? Is there any structure to the samples (evenly spaced)? One route is to use a change of basis (wavelets, FFT, etc.) to work where the function may have a sparse representation. Then use any old numerical integration routine like quasi-monte carlo or even regular monte carlo. If your samples have structure, there may be a more efficient method.
– dls
Jan 28 '12 at 20:03
• Well, the samples originate from a physical simulation, no analytic expression. You may assume them to be evenly spaced. Fourier transform won't give a sparse representation, I'm afraid there is no known base that would yield sparse representation. Jan 28 '12 at 20:21
• So you're currently not storing the simulation output, i.e. the function samples? Is there even a requirement to store the function? Do you have control over the sampling process? Since they're evenly spaced, why not just walk around the domain in little chunks and use a quadrature rule? Minimal storage required. If you have control over sampling process, and samples can be freely generated, you open yourself up to adaptive algorithms which will find interesting areas of the integrand. This is a very common situation.
– dls
Jan 28 '12 at 20:39
• You might also want to check out the answers to this question.
– Dan
Jan 29 '12 at 4:56

Sparse tensor grids are a common and rigorously analyzed approach. For appropriate classes of functions, sparse grids reduce storage requirements from $\mathcal O(n^d)$ for a full tensor-product grid to $\mathcal O(C^d n \log^{d-1} n)$ with (usually) small value of $C$. This is a very active field, especially as it pertains to stochastic partial differential equations (SPDEs). These review papers are good sources.