# sparse_grid_hw

sparse_grid_hw, a MATLAB code which can compute sparse grids for multidimensional integration, based on 1D rules for the unit interval with unit weight function, or for the real line with the Gauss-Hermite weight function. The original version of the code is by Florian Heiss and Viktor Winschel.

The original version of this software, and other information, is available at https://sparse-grids.de .

Four built-in 1D families of quadrature rules are supplied, and the user can extend the package by supplying any family of 1D quadrature rules.

The built-in families are identified by a 3-letter key which is also the name of the MATLAB function that returns members of the family:

• gqu, standard Gauss-Legendre quadrature rules, for the unit interval [0,1], with weight function w(x) = 1.
• gqn, standard Gauss-Hermite quadrature rules, for the infinite interval (-oo,+oo), with weight function w(x) = exp(-x*x/2)/sqrt(2*pi).
• kpu, Kronrod-Patterson quadrature rules, for the unit interval [0,1], with weight function w(x) = 1. These sacrifice some of the precision of gqu in order to provide a family of nested rules.
• kpn, Kronrod-Patterson quadrature rules, for the infinite interval (-oo,+oo), with weight function w(x) = exp(-x*x/2)/sqrt(2*pi). These sacrifice some of the precision of gqn in order to provide a family of nested rules.

The user can build new sparse grids by supplying a 1D quadrature family. Examples provided include:

• ccu, Clenshaw-Curtis quadrature rules, for the unit interval [0,1], with weight function w(x) = 1. The K-th call returns the rule of order 1 if K is 1, and 2*(K-1)+1 otherwise.
• ccs, slow Clenshaw-Curtis quadrature rules, for the unit interval [0,1], with weight function w(x) = 1. The K-th call returns the rule of order 1 if K is 1, and otherwise a rule whose order N has the form 2^E+1 and is the lowest such order with precision at least 2*K-1.
• glo, Gauss-Legendre odd quadrature rules, for the unit interval [0,1], with weight function w(x) = 1. The K-th call returns the rule of order 2*(K/2)+1.

### Languages:

sparse_grid_hw is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version

### Related Data and Programs:

grid_display, a MATLAB code which can display a 2d or 3d grid or sparse grid.

nint_exactness_mixed, a MATLAB code which measures the polynomial exactness of a multidimensional quadrature rule based on a mixture of 1d quadrature rule factors.

product_rule, a MATLAB code which constructs a product quadrature rule from identical 1d factor rules.

quadrule, a MATLAB code which defines quadrature rules for various intervals and weight functions.

sparse_grid_cc, a MATLAB code which can define a multidimensional sparse grid based on a 1d clenshaw curtis rule.

sparse_grid_gl, a MATLAB code which creates sparse grids based on gauss-legendre rules.

sparse_grid_hermite, a MATLAB code which creates sparse grids based on gauss-hermite rules.

sparse_grid_laguerre, a MATLAB code which creates sparse grids based on gauss-laguerre rules.

spinterp, a MATLAB code which carries out piecewise multilinear hierarchical sparse grid interpolation; an earlier version of this software is acm toms algorithm 847, by andreas klimke;

spquad, a MATLAB code which computes the points and weights of a sparse grid quadrature rule for a multidimensional integral, based on the clenshaw-curtis quadrature rule, by greg von winckel.

### Author:

Original MATLAB code by Florian Heiss and Viktor Winschel.

### Reference:

Fully symmetric interpolatory rules for multiple integrals over infinite regions with Gaussian weight,
Journal of Computational and Applied Mathematics,
Volume 71, 1996, pages 299-309.
• Florian Heiss, Viktor Winschel,
Likelihood approximation by numerical integration on sparse grids,
Journal of Econometrics,
Volume 144, Number 1, May 2008, pages 62-80.
• Thomas Patterson,
Mathematics of Computation,
Volume 22, Number 104, October 1968, pages 847-856.
• Knut Petras,
Smolyak Cubature of Given Polynomial Degree with Few Nodes for Increasing Dimension,
Numerische Mathematik,
Volume 93, Number 4, February 2003, pages 729-753.

### Source Code:

• cc.m returns one rule from the CCU family defined on [-1,+1] with unit weight, indexed by order.
• cce.m returns one rule from the CCU (Clenshaw-Curtis Exponential growth) family defined on [-1,+1] with unit weight, indexed by level.
• cce_order.m computes the order of a Clenshaw-Curtis Exponential (CCE) rule from the level.
• ccl.m returns one rule from the CCL (Clenshaw-Curtis Linear growth) family defined on [-1,+1] with unit weight, indexed by level.
• ccl_order.m computes the order of a CCL (Clenshaw-Curtis Linear growth) rule from the level.
• ccs.m returns one rule from the CCS (Clenshaw-Curtis Slow growth) family defined on [-1,+1] with unit weight, indexed by level.
• ccs_order.m computes the order of a CCS (Clenshaw Curtis Slow growth) rule from the level.
• get_seq.m generates integer vectors that describe component tensor products.
• gqn.m returns one rule from the GQN family.
• gqn_order.m computes the order of a GQN rule from the level, N = L.
• gqn2_order.m computes the order of a GQN rule from the level, N = 2*L-1.
• gqu.m returns one rule from the GQU family.
• gqu_order.m computes the order of a GQU rule from the level.
• i4_factorial2.m computes the double factorial function.
• i4vec_print.m prints an I4VEC.
• kpn.m returns one rule from the KPN family.
• kpn_order.m returns the order of a member of the KPN family given the level.
• kpu.m returns one rule from the KPU family.
• kpu_order.m returns the order of a member of the KPU family given the level.
• nwspgr.m the main routine, which the user calls in order to compute a particular sparse grid.
• nwspgr_size.m returns the size of a particular sparse grid.