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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – dls
    Jan 28, 2012 at 20:03
  • $\begingroup$ 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. $\endgroup$
    – Yrogirg
    Jan 28, 2012 at 20:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – dls
    Jan 28, 2012 at 20:39
  • $\begingroup$ You might also want to check out the answers to this question. $\endgroup$
    – Dan
    Jan 29, 2012 at 4:56

1 Answer 1


First, recognize than the functions you are working with must have some decay for any "efficient" method to be possible. If your functions have rich structure in all modes of the full tensor product, then you can't do better. But many functions of interest have decay in their mixed derivatives, in which case efficient methods are available. The term "separation rank" is sometimes used to refer to how many mixed derivatives are needed.

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.

For some problems in dimensions around 6, some physics applications use particle, particle-in-cell, or even naive discretizations of the space (e.g. spherical harmonics to discretize a distribution in angle space at every grid cell in physical space). These methods don't have the quasi-optimality with respect to dimension that the sparse grid techniques have, but they don't require any particular decay (low separation rank).

If you don't need to perform general manipulations of the functions, but instead want to determine some specific properties, there may be other ways to formulate the question to avoid needing to represent it in these ways.

  • $\begingroup$ Jed, are you aware of any application of these techniques to molecular simulation of liquids? I mean classical, not quantum, for example finding thermodynamic properties of a substance by an intermolecular potential. Can they substitute ordinary molecular dynamics or Monte-Carlo methods? $\endgroup$
    – Yrogirg
    Feb 4, 2012 at 5:31

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.