Popularity
13 Stars
Updated Last
8 Months Ago
Started In
October 2015

# SparseGrids

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

## Installation

In Julia switch to `Pkg` with `]` and run

`add SparseGrids`

## Usage

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`.

## References

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.

## ToDos

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]

### Used By Packages

No packages found.