This package computes sparse grids for quadrature rules used to compute multidimensional integrals.

In Julia, run

```
Pkg.add("SparseGrids")
```

If `f`

is a function that returns `nodes, weights = f(n)`

, for any (integer) order `n`

, then the function `sparsegrid`

computes the sparse extension to `D`

dimensions of order `O`

:

```
nodes, weigths = sparsegrid(D, O, f)
```

By default, `f`

is `gausshermite`

from the FastGaussQuadrature package.
The `gausshermite`

quadrature rule is used for computing integrals over `R^D`

with integrants of the form `g(x) * exp(-|x|^2)`

.
To approximate such an integral, compute

```
dot( weigths, g(nodes) )
```

Note that when integrating against `exp(-|x|^2)`

instead of the standard Gaussian density, the nodes and weigths are rescaled compared to e.g. the source of the Kronrod-Patterson nodes mentioned below.

This package offers another node generating function for "Gaussian" integrals, `kpn`

, for the *nested* Kronrod-Patterson nodes.
When the 1D nodes are nested, the higher dimensional sparse grids contain fewer points.

The easy extension of 1D nodes (where the number of nodes also grows *much* faster) is by tensor products.
This is available by the function `tensorgrid`

that takes the same inputs as `sparsegrid`

.

The sparse grid quadrature rules are described in e.g.

- Thomas Gerstner, Michael Griebel, "Numerical integration using sparse grids", Numerical Algorithms, 1998, 209--232. DOI: 10.1023/A:1019129717644
- Florian Heiss, Victor Winschel, "Likelihood approximation by numerical integration on sparse grids", Journal of Econometrics, 2008, vol. 144, pp. 62--80. DOI: 10.1016/j.jeconom.2007.12.004
- Vesa Kaarnioja, "Smolyak Quadrature", Master's thesis, University of Helsinki, 2013.

The Matlab scripts released in connection with the paper by Heiss & Winschel have also served as an inspiration in the implementation. These are found at http://www.sparse-grids.de. Note that there are some disagreements between these Matlab scripts and the paper; the Matlab scripts are correct, as confirmed by testing.

The algorithm for computing the integer D-vectors with constant 1-norm is found in e.g. Kaarnioja's thesis as Algorithm 1.11.

The nested nodes are obtained from the sparse-grids web page.

At some point methods for *computing* nested nodes may be implemented using techniques from e.g.

- Sanjay Mehrotra, David Papp, "Generating nested quadrature formulas for general weight functions with known moments" arXiv: 1203.1554 [math.NA]

10/08/2015

9 months ago

57 commits