sparse_grid_hw

sparse_grid_hw, a Fortran77 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 MATLAB code is by Florian Heiss and Viktor Winschel.

The Fortran77 version of the library is only partially complete. Completion of the translation has been held up by the fact that Fortran77 does not "officially" support allocatable arrays, and so the sizes of certain arrays must be determined and allocated in advance.

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 routine 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:

• cce_order, Clenshaw-Curtis Exponential 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.
• ccl_order, Clenshaw-Curtis Linear 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-1.
• ccs_order, slow Clenshaw-Curtis Slow 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 MIT license

Languages:

sparse_grid_hw is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version.

Related Data and Programs:

sparse_grid_hw_test

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

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

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

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

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

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

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_HERMITE, a Fortran90 library which creates sparse grids based on Gauss-Hermite 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. Fortran77 version by John Burkardt.

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, Number 1, May 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:

• sparse_grid_hw.f, the source code.
• sparse_grid_hw.sh, BASH commands to compile the source code.