SPARSE_GRID_MIXED_GROWTH
Sparse Grids, Mixed Factors, Growth Rules

SPARSE_GRID_MIXED_GROWTH is a C++ library which can be used to construct a sparse grid whose factors are possibly distinct 1D quadrature rules.

SPARSE_GRID_MIXED_GROWTH is an experimental version of SPARSE_GRID_MIXED. It includes an option to specify the growth rule that converts a level (which indexes the sparse grids) to the order (which counts the number of points in a 1D rule.) The standard rule is exponential, but we are considering the effect of a simple linear rule.

For the Clenshaw Curtis rule, exponential growth means that

• level 0 has order 1;
• level L has order 2^L+1, for L greater than 0;

For all other rules, exponential growth means that

• level L has order 2^(L+1)-1;

For all rules, linear growth means that

• level L has order 2*L+1;

Linear growth is not available for the Gauss-Patterson rule.

The user controls the growth rate by setting an additional argument whose dummy name is level_to_order, and which represents a pointer to a function which determines the relationship between the level of a 1D quadrature rule and the order, or number of points, that it uses:

• level_to_order_default uses the original exponential growth rate for the fully nested rules ("CC", "F2" and "GP"), and a simple linear growth rate for other rules ("GL", "GH", "GGH", "LG", "GLG", "GJ" and "GW").
• level_to_order_exponential uses the original exponential growth rate for all rules.
• level_to_order_linear uses the simple linear growth rate for all rules.

The 1D quadrature rules are designed to approximate an integral of the form:

Integral ( A < X < B ) F(X) W(X) dX

Sum ( 1 <= I <= ORDER) F(X(I)) * W(I)

Note that the letter W, unfortunately, is used to denote both the weight function in the original integral, and the vector of weight values in the quadrature sum.

The following list includes 1D quadrature rules that may be specified as factors. These rules are computed by the SANDIA_RULES library, which must be accessible when SPARSE_GRID_MIXED_GROWTH is being used.

1. CC, Clenshaw-Curtis:
   defined on [-1,+1], with w(x)=1,
   a closed, fully nested rule.
2. F2, Fejer Type 2:
   defined on (-1,+1), with w(x)=1,
   an open, fully nested rule.
3. GP, Gauss Patterson:
   defined on (-1,+1), with w(x)=1,
   a family of the midpoint rule, the 3 point Gauss Legendre rule, and then successive Patterson refinements,
   an open, fully nested rule.
4. GL, Gauss Legendre:
   defined on (-1,+1), with w(x)=1,
   an open, weakly nested rule.
5. GH, Gauss Hermite:
   defined on (-oo,+oo), with w(x)=exp(-x*x),
   an open, weakly nested rule.
6. GGH, Generalized Gauss Hermite:
   defined on (-oo,+oo), with w(x)=|x|^alpha * exp(-x*x),
   an open, weakly nested rule.
7. LG, Gauss Laguerre:
   defined on (0,+oo) with w(x)=exp(-x),
   an open, non-nested rule.
8. GLG, Generalized Gauss Laguerre:
   defined on (0,+oo) with w(x)=x^alpha * exp(-x),
   an open, non-nested rule.
9. GJ, Gauss Jacobi:
   defined on [-1,+1] with w(x)=(1-x)^alpha (1+x)^beta
   an open, non-nested rule.
10. GW, Golub Welsch:
    a rule defined by the user based on the Golub-Welsch algorithm,
    with points and weights supplied by external routines,
    presumably an open, non-nested rule.
    (not supported yet)

A sparse grid is a quadrature rule for a multidimensional integral. It is formed by taking a certain linear combination of lower-order product rules. The product rules, in turn, are formed as direct products of 1D quadrature rules. It is common to form a sparse grid in which the 1D component quadrature rules are the same. This package, however, is intended to produce sparse grids based on sums of product rules for which the rule chosen for each spatial dimension may be freely chosen from the set listed above.

These sparse grids are still indexed by a number known as level, and assembled as a sum of low order product rules. As the value of level increases, the point growth becomes more complicated. This is because the 1D rules have somewhat varying point growth patterns to begin with, and the varying levels of nestedness have a dramatic effect on the sparsity of the total grid.

Since a sparse grid is made up of a combination of product grids, it is frequently the case that many of the product grids include the same point. For efficiency, it is usually desirable to merge or consolidate such duplicate points when expressing the resulting sparse grid rule. It is possible to "logically" determine when a duplicate point will be generated; however, this logic changes depending on the specific 1-dimensional rules being used, and the tests can become quite elaborate. Moreover, for rules which include real parameters, the determination of duplication can require a numerical tolerance.

In order to simplify the matter of the detection of duplicate points, the codes presented begin by generating the entire "naive" set of points. Then a user-specified tolerance TOL is used to determine when two points are equal. If the maximum difference between any two components is less than or equal to TOL, the points are declared to be equal.

A reasonable value for TOL might be the square root of the machine precision. Setting TOL to zero means that only points which are identical to the last significant digit are taken to be duplicates. Setting TOL to a negative value means that no duplicate points will be eliminated - in other words, this choice produces the full or "naive" grid.

Licensing:

The code described and made available on this web page is distributed under the GNU LGPL license.

Related Data and Programs:

CLENSHAW_CURTIS is a C++ library which computes Clenshaw Curtis grids in multiple dimensions, as well as sparse grids formed from sums of Clenshaw Curtis grids.

NINT_EXACTNESS_MIXED is a C++ program which measures the polynomial exactness of a multidimensional quadrature rule based on a mixture of 1D quadrature rule factors.

PRODUCT_FACTOR is a C++ program which constructs a product quadrature rule from distinct 1D factor rules.

PRODUCT_RULE is a C++ program which constructs a product quadrature rule from identical 1D factor rules.

QUADRULE is a C++ library which defines quadrature rules for various intervals and weight functions.

SANDIA_RULES, a C++ library which produces 1D quadrature rules of Chebyshev, Clenshaw Curtis, Fejer 2, Gegenbauer, generalized Hermite, generalized Laguerre, Hermite, Jacobi, Laguerre, Legendre and Patterson types.

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

SMOLPACK is 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 is a C++ library which can define a multidimensional sparse grid based on a 1D Clenshaw Curtis rule.

SPARSE_GRID_CLOSED, a C++ library which creates sparse grids based on closed rules (Clenshaw-Curtis, Newton-Cotes-Closed).

SPARSE_GRID_DISPLAY is a MATLAB program which can display a 2D or 3D sparse grid.

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

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

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

SPARSE_GRID_MIXED, a C++ library which creates sparse grids based on a mix of 1D rules.

SPARSE_GRID_MIXED_GROWTH, a dataset directory which contains multidimensional Smolyak sparse grids based on a mixed set of 1D factor rules and a choice of growth rules.

SPARSE_GRID_OPEN, a C++ library which creates sparse grids based on open rules (Fejer 2, Gauss-Patterson, Newton-Cotes-Open).

SPINTERP is a MATLAB library which uses a sparse grid to perform multilinear hierarchical interpolation, by Andreas Klimke.

Reference:

1. Milton Abramowitz, Irene Stegun,
   Handbook of Mathematical Functions,
   National Bureau of Standards, 1964,
   ISBN: 0-486-61272-4,
   LC: QA47.A34.
2. Charles Clenshaw, Alan Curtis,
   A Method for Numerical Integration on an Automatic Computer,
   Numerische Mathematik,
   Volume 2, Number 1, December 1960, pages 197-205.
3. Philip Davis, Philip Rabinowitz,
   Methods of Numerical Integration,
   Second Edition,
   Dover, 2007,
   ISBN: 0486453391,
   LC: QA299.3.D28.
4. Walter Gautschi,
   Numerical Quadrature in the Presence of a Singularity,
   SIAM Journal on Numerical Analysis,
   Volume 4, Number 3, September 1967, pages 357-362.
5. Thomas Gerstner, Michael Griebel,
   Numerical Integration Using Sparse Grids,
   Numerical Algorithms,
   Volume 18, Number 3-4, 1998, pages 209-232.
6. Gene Golub, John Welsch,
   Calculation of Gaussian Quadrature Rules,
   Mathematics of Computation,
   Volume 23, Number 106, April 1969, pages 221-230.
7. Prem Kythe, Michael Schaeferkotter,
   Handbook of Computational Methods for Integration,
   Chapman and Hall, 2004,
   ISBN: 1-58488-428-2,
   LC: QA299.3.K98.
8. Albert Nijenhuis, Herbert Wilf,
   Combinatorial Algorithms for Computers and Calculators,
   Second Edition,
   Academic Press, 1978,
   ISBN: 0-12-519260-6,
   LC: QA164.N54.
9. Thomas Patterson,
   The Optimal Addition of Points to Quadrature Formulae,
   Mathematics of Computation,
   Volume 22, Number 104, October 1968, pages 847-856.
10. Sergey Smolyak,
    Quadrature and Interpolation Formulas for Tensor Products of Certain Classes of Functions,
    Doklady Akademii Nauk SSSR,
    Volume 4, 1963, pages 240-243.
11. Arthur Stroud, Don Secrest,
    Gaussian Quadrature Formulas,
    Prentice Hall, 1966,
    LC: QA299.4G3S7.
12. Joerg Waldvogel,
    Fast Construction of the Fejer and Clenshaw-Curtis Quadrature Rules,
    BIT Numerical Mathematics,
    Volume 43, Number 1, 2003, pages 1-18.

Source Code:

• sparse_grid_mixed_growth.C, the source code.
• sparse_grid_mixed_growth.H, the include file.
• sparse_grid_mixed_growth.csh, commands to compile the source code.

Examples and Tests:

• sparse_grid_mixed_growth_test.C, a sample calling program.
• sparse_grid_mixed_growth_test.csh, commands to compile and run the sample program.
• sparse_grid_mixed_growth_test.txt, the output file.

List of Routines:

• LEVEL_TO_ORDER_DEFAULT: 1D level to order, default growth rates.
• LEVEL_TO_ORDER_EXPONENTIAL: 1D level to order with exponential growth.
• LEVEL_TO_ORDER_LINEAR: 1D level to order with linear growth.
• PRODUCT_MIXED_GROWTH_WEIGHT computes the weights of a mixed product rule.
• SPARSE_GRID_MIXED_GROWTH_INDEX indexes a sparse grid of mixed 1D rules.
• SPARSE_GRID_MIXED_GROWTH_POINT computes the points of a sparse grid rule.
• SPARSE_GRID_MIXED_GROWTH_SIZE sizes a sparse grid, discounting duplicates.
• SPARSE_GRID_MIXED_GROWTH_SIZE_TOTAL sizes a sparse grid, counting duplicates.
• SPARSE_GRID_MIXED_GROWTH_UNIQUE_INDEX maps nonunique to unique points.
• SPARSE_GRID_MIXED_GROWTH_WEIGHT: sparse grid weights based on a mix of 1D rules.
• SPARSE_GRID_MIXED_GROWTH_WRITE writes a sparse grid rule to five files.

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