SPARSE_GRID_HW
Sparse Grids for Uniform and Normal Weights
Heiss and Winschel

SPARSE_GRID_HW is a MATLAB library 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 code is by Florian Heiss and Viktor Winschel.

The original version of this software, and other information, is available at http://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.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

SPARSE_GRID_HW is available in a FORTRAN90 version and a MATLAB version

Related Data and Programs:

GRID_DISPLAY, a MATLAB library which can display a 2D or 3D grid or sparse grid.

NINT_EXACTNESS_MIXED, a MATLAB program which measures the polynomial exactness of a multidimensional quadrature rule based on a mixture of 1D quadrature rule factors.

PRODUCT_RULE, a MATLAB program which constructs a product quadrature rule from identical 1D factor rules.

QUADRULE, a MATLAB library which defines quadrature rules for various intervals and weight functions.

SANDIA_RULES, a MATLAB library which generates Gauss quadrature rules of various orders and types.

SANDIA_SPARSE, a MATLAB library which computes the points and weights of a Smolyak sparse grid, based on a variety of 1-dimensional quadrature rules.

SGMGA, a MATLAB library which creates sparse grids based on a mixture of 1D quadrature rules, allowing anisotropic weights for each dimension.

SMOLPACK, a C library which implements Novak and Ritter's method for estimating the integral of a function over a multidimensional hypercube using sparse grids, by Knut Petras.

SPARSE_GRID_CC, a MATLAB library which can define a multidimensional sparse grid based on a 1D Clenshaw Curtis rule.

SPARSE_GRID_GL, a MATLAB library which creates sparse grids based on Gauss-Legendre rules.

SPARSE_GRID_HERMITE, a MATLAB library which creates sparse grids based on Gauss-Hermite rules.

SPARSE_GRID_LAGUERRE, a MATLAB library which creates sparse grids based on Gauss-Laguerre rules.

SPARSE_GRID_MIXED, a MATLAB library which creates a sparse grid dataset based on a mixed set of 1D factor rules.

SPINTERP, a MATLAB library which carries out piecewise multilinear hierarchical sparse grid interpolation; an earlier version of this software is ACM TOMS Algorithm 847, by Andreas Klimke;

Author:

Original MATLAB code by Florian Heiss and Viktor Winschel.

Reference:

• Alan Genz, Bradley Keister,
  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, 2008, pages 62-80.
• Thomas Patterson,
  The optimal addition of points to quadrature formulae,
  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:

• ccu.m returns one rule from the CCU family defined on [-1,+1] with unit weight.
• ccu_order.m computes the order of a CCU 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.
• 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.
• quad_rule_print.m prints a multidimensional quadrature rule.
• r8vecs_print.m, prints a packed R8VEC.
• rules_1d_set.m sets the packed vectors of 1D nodes and weights.
• rules_1d_size.m determines the size of the packed RULES_1D array.
• symmetric_sparse_size.m sizes a symmetric sparse rule.
• tensor_product.m computes a tensor product quadrature rule.
• timestamp.m is a script which prints a timestamp;

Examples and Tests:

• sparse_grid_hw_test.m calls all the tests.
• sparse_grid_hw_test_output.txt the output file;
• ccs_test.m uses the CCS function for 1D quadrature.
• ccu_sparse_test.m uses the CCU function to build a sparse grid.
• ccu_test.m uses the CCU function for 1D quadrature.
• fn_integral.m evaluates the exact integral of the Hermite test function.
• fn_value.m is a Hermite test function.
• fu_integral.m evaluates the exact integral of a test function over [0,1]^D.
• fu_value.m is a test function over [0,1]^D.
• get_seq_test.m tests GET_SEQ.
• gqn_sparse_test.m uses the GQN function to build a sparse grid.
• gqn_test.m uses the GQN function for 1D quadrature.
• gqu_sparse_test.m uses the GQU function to build a sparse grid.
• gqu_test.m uses the GQU function for 1D quadrature.
• kpn_sparse_test.m uses the KPN function to build a sparse grid.
• kpn_test.m uses the KPN function for 1D quadrature.
• kpu_sparse_test.m uses the KPU function to build a sparse grid.
• kpu_test.m uses the KPU function for 1D quadrature.
• nwspgr_size_test.m tests NWSPGR_SIZE.
• nwspgr_test.m tests NWSPGR.
• order_report.m reports on the precision and order of all rules.
• pack_rules_test.m tests RULES_1D_SIZE and RULES_1D_SET.
• symmetric_sparse_size_test.m tests SYMMETRIC_SPARSE_SIZE_TEST.
• tensor_product_test.m tests TENSOR_PRODUCT_TEST.

You can go up one level to the MATLAB source codes.