SMOLPACK
Multidimensional Quadrature Using Sparse Grids

SMOLPACK is a C library which estimates the integral of a function over a hypercube using a sparse grid, by Knut Petras.

An interactive test program is also provided. The user can specify the input to this program as part of the commandline, or wait to enter the data interactively.

Output from the program includes the exact and approximate integral values, the error, and, if requested, the number of quadrature points (function evaluations) and the number of quadrature weights that needed to be computed. Note that, because of symmetry in the quadrature rule, the number of quadrature weights computed will generally be much lower than the number of quadrature points.

Usage:

smolpack_interactive fnum dim k seed bs

• fnum is the test function f(x) to be integrated.
  1 <= fnum <= 7
• dim is the spatial dimension,
  1 <= dim < 40
• k is the number of stages. Generally a "small" number like 4 or 8;
  1 <= k
• seed is a seed for the random number generator. Should not be zero!
• bs is the "basic sequence", that is, the one dimensional quadrature rule that is used to build the multidimensional quadrature rule. The two choices are:
  • bs = 1: delayed Clenshaw Curtis, uses few function evaluations;
  • bs = 2: standard Clenshaw Curtis;

Test Functions:

SMOLPACK_INTERACTIVE allows the user to choose a test function to be integrated. The first six test functions come from the standard test suite of Genz. In the description, M denotes the spatial dimension, R is a randomly chosen parameter, C is a randomly chosen scaling vector, and X0 is a randomly chosen displacement vector.

1. f(x) = cos ( 2 * pi * r + sum ( c(1:m) * x(1:m) ) ),
   Genz "Oscillatory";
2. f(x) = 1 / product ( c(1:m)^2 + (x(1:m) - x0(1:m))^2),
   Genz "Product Peak";
3. f(x) = 1 / ( 1 + sum ( c(1:m) * x(1:m) ) )^(d+1),
   Genz "Corner Peak";
4. f(x) = exp(-sum(c(1:m)^2 * ( x(1:m) - x0(1:m))^2 ) ),
   Genz "Gaussian";
5. f(x) = exp ( - sum ( c(1:m) * abs ( x(1:m) - x0(1:m) ) ) ),
   Genz "Continuous";
6. f(x) = exp(sum(c(1:m)*x(1:m)) for x(1:2) <= x0(1:2), 0 otherwise,
   Genz "Discontinuous";
7. f(x) = exp(sum( x(1:m));

Languages:

SMOLPACK is available in a C version.

Related Programs:

CC_DISPLAY, a MATLAB program which can compute and display Clenshaw Curtis grids in two dimensions, as well as sparse grids formed from sums of Clenshaw Curtis grids.

CLENSHAW_CURTIS_RULE, a C library which can set up a Clenshaw Curtis quadrature grid in multiple dimensions.

SPARSE_GRID, a PYTHON library which contains classes and functions defining sparse grids, by Jochen Garcke.

SPARSE_GRID_CC, a dataset directory which contains files of the abscissas of sparse grids based on a Clenshaw Curtis rule.

SPARSE_GRID_F2, a dataset directory which contains files of the abscissas of sparse grids based on a Fejer Type 2 rule.

SPARSE_GRID_GP, a dataset directory which contains files of the abscissas of sparse grids based on a Gauss Patterson rule.

SPARSE_GRID_HW, a C library which creates sparse grids based on Gauss-Legendre, Gauss-Hermite, Gauss-Patterson, or a nested variation of Gauss-Hermite rules, by Florian Heiss and Viktor Winschel.

SPQUAD, a MATLAB library 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.

TOMS847, a MATLAB program which uses sparse grids to carry out multilinear hierarchical interpolation. It is commonly known as SPINTERP, and is by Andreas Klimke.

TESTPACK, a C library which defines the Genz test integrand functions.

TEST_NINT, a FORTRAN90 library which defines a number of test integrand functions for multidimensional integration.

Author:

Knut Petras

Reference:

1. Alan Genz,
   A Package for Testing Multiple Integration Subroutines,
   in Numerical Integration: Recent Developments, Software and Applications,
   edited by Patrick Keast, Graeme Fairweather,
   Reidel, 1987, pages 337-340,
   ISBN: 9027725144,
   LC: QA299.3.N38
2. Erich Novak, Klaus Ritter,
   High dimensional integration of smooth functions over cubes,
   Numerische Mathematik,
   Volume 75, Number 1, November 1996, pages 79-97.
3. Erich Novak, Klaus Ritter,
   Simple Cubature Formulas with High Polynomial Exactness,
   Constructive Approximation,
   Volume 15, Number 4, December 1999, pages 499-522.
4. Knut Petras,
   Fast Calculation of Coefficients in the Smolyak Algorithm,
   Numerical Algorithms,
   Volume 26, Number 2, February 2001, pages 93-109.
5. 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.
6. Sergey Smolyak,
   Quadrature and Interpolation Formulas for Tensor Products of Certain Classes of Functions,
   Doklady Akademii Nauk SSSR,
   Volume 4, 1963, pages 240-243.

Source Code:

• ccsmolyak.c, sparse integration using standard Clenshaw Curtis rules.
• smolyak.c, sparse integration using delayed Clenshaw Curtis rule.
• smolpack.h, the include file.

Examples and Tests:

• smolpack_interactive.c, an interactive test program.
• problem1_output.txt, output from the test program related to test function 1;
• problem2_output.txt, output from the test program related to test function 2;
• problem3_output.txt, output from the test program related to test function 3;
• problem4_output.txt, output from the test program related to test function 4;
• problem5_output.txt, output from the test program related to test function 5;
• problem6_output.txt, output from the test program related to test function 6;
• problem7_output.txt, output from the test program related to test function 7;

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