SparseGrids

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

In Julia switch to Pkg with ] and run

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]