sgmg, a C++ code which constructs a sparse grid whose factors are possibly distinct 1D quadrature rules.
sgmg() is the successor to the SPARSE_GRID_MIXED library. 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.)
sgmg() calls many routines from the SANDIA_RULES library. Source code or compiled copies of both libraries must be available when a code wishes to use the SGMG library.
Note that there is a variation of this library which is available, called SANDIA_SGMG. The variant code has the same capabilities, but uses a different interface when it calls the functions in SANDIA_RULES that generate points and weights of quadrature rules.
Sparse grids are organized by a series of levels, with level 0 being the simplest grid. Sparse grids are generated by weighted sums of product rules. Each product rule is formed by the product of 1D quadrature rules. The 1D quadrature rules also have levels, starting with 0. Although the 1D quadrature rule is probably available in versions of any order (number of points), the sparse grid will usually be based on a selection of these 1D rules. These rules are indexed by a 1D level. The relationship between the 1D level and the actual order of the 1D quadrature rule is somewhat arbitrary. In most cases, if we can guarantee that the the 1D quadrature rule of level L has 1D polynomial precision 2*L+1, then we can deduce that the sparse grid of level L will also have polynomial precision 2*L+1. It doesn't hurt for the 1D rule to have greater precision than that, but if this minimal precision is not achieved, then the precision of the sparse grid rule cannot be guaranteed.
This code allows the user a great deal of flexibility in choosing the growth rules, that is, the formula that determines the order O of a 1D quadrature rule of 1D level L.
The user may be familiar with the typical sparse grid associated with the 1D Clenshaw-Curtis rule, for which the growth rule may be termed "exponential". Specifically, for this growth rule, we have
For Gauss rules, the typical exponential growth is similar:
However, these growth rules very quickly produce 1D quadrature rules of excessive order. So this package allows the user to request variations of the growth rules, including:
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:
The 1D quadrature rules are designed to approximate an integral of the form:
Integral ( A < X < B ) F(X) W(X) dXwhere W(X) is a weight function, by the quadrature sum:
Sum ( 1 <= I <= ORDER) F(X(I)) * W(I)where the set of X values are known as abscissas and the set of W values are known as weights.
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.
| Index | Name | Abbreviation | Default Growth Rule | Interval | Weight function |
|---|---|---|---|---|---|
| 1 | Clenshaw-Curtis | CC | Moderate Exponential | [-1,+1] | 1 |
| 2 | Fejer Type 2 | F2 | Moderate Exponential | [-1,+1] | 1 |
| 3 | Gauss Patterson | GP | Moderate Exponential | [-1,+1] | 1 |
| 4 | Gauss-Legendre | GL | Moderate Linear | [-1,+1] | 1 |
| 5 | Gauss-Hermite | GH | Moderate Linear | (-oo,+oo) | e-x*x |
| 6 | Generalized Gauss-Hermite | GGH | Moderate Linear | (-oo,+oo) | |x|alpha e-x*x |
| 7 | Gauss-Laguerre | LG | Moderate Linear | [0,+oo) | e-x |
| 8 | Generalized Gauss-Laguerre | GLG | Moderate Linear | [0,+oo) | xalpha e-x |
| 9 | Gauss-Jacobi | GJ | Moderate Linear | [-1,+1] | (1-x)alpha (1+x)beta |
| 10 | Hermite Genz-Keister | HGK | Moderate Exponential | (-oo,+oo) | e-x*x |
| 11 | User Supplied Open | UO | Moderate Linear | ? | ? |
| 12 | User Supplied Closed | UC | Moderate Linear | ? | ? |
For a given family, a growth rule can be prescribed, which determines the orders O of the sequence of rules selected from the family. The selected rules are indexed by L, which starts at 0. The polynomial precision P of the rule is sometimes used to determine the appropriate order O.
| Index | Name | Order Formula |
|---|---|---|
| 0 | "DF", Default | moderate exponential or moderate linear |
| 1 | "SL", Slow linear | O=L+1 |
| 2 | "SO", Slow Linear Odd (always use a rule of oddd order) | O=1+2*((L+1)/2) |
| 3 | "ML", Moderate Linear | O=2L+1 |
| 4 | "SE", Slow Exponential | select smallest exponential order O so that 2L+1 <= P |
| 5 | "ME", Moderate Exponential | select smallest exponential order O so that 4L+1 <= P |
| 6 | "FE", Full Exponential | O=2^L+1 for Clenshaw Curtis, O=2^(L+1)-1 otherwise. |
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.
A multidimensional sparse grid rule is defined in terms of the 1D quadrature rules used in each dimension. This library provides 9 such standard rules. If rule[dim] is between 1 and 9, then the appropriate internal routines are called to compute the points and weights, and assumptions are also made about the growth rate in the rule.
The user may wish to define other quadrature rules, and to combine these with the built-in rules. Such rules are assumed to be generated by the Golub Welsch procedure. To build a sparse grid rule which uses a Golub Welsch rule in dimension dim, the user must do the following:
1) Set rule[dim]=10 to indicate that a Golub Welsch rule is being used in this dimension. The user may send parameters to this rule by setting np and p.
2) Write a point function of the form
void compute_points ( int order, int np, double p[], double points[] )
which may use np parameter values in the p vector as parameters
for the rule, computing the points of the rule of order order and
returning them in the array points[];
3) Write a weight function of the form
void compute_weights ( int order, int np, double p[], double weights[] )
which may use np parameter values in the p vector as parameters
for the rule, computing the weights of the rule of order order and
returning them in the array weights[];
The code knows a lot about sparse grid rules which are built entirely from the predefined internal rules. On the other hand, if even a single component of the sparse grid rule involves a user-defined Golub-Welsch rule, there are some things the code does not know how to do. Generally, these are minor issues, but the user should be aware of them. In particular:
A version of the sparse grid library is available in https://tasmanian.ornl.gov, the TASMANIAN library, available from Oak Ridge National Laboratory.
The information on this web page is distributed under the MIT license.
sgmg is available in a C++ version.
nint_exactness_mixed, a C++ code which measures the polynomial exactness of a multidimensional quadrature rule based on a mixture of 1D quadrature rule factors.
quad_rule, a C++ code which defines quadrature rules for various intervals and weight functions.
sandia_rules, a C++ code which produces 1D quadrature rules of Chebyshev, Clenshaw Curtis, Fejer 2, Gegenbauer, generalized Hermite, generalized Laguerre, Hermite, Jacobi, Laguerre, Legendre and Patterson types.
sandia_sgmg, a C++ code which creates a sparse grid dataset based on a mixed set of 1D factor rules, and experiments with the use of a linear growth rate for the quadrature rules. This is a version of SGMG that uses a different procedure for supplying the parameters needed to evaluate certain quadrature rules.
sandia_sparse, a C++ code which computes the points and weights of a Smolyak sparse grid, based on a variety of 1-dimensional quadrature rules.
sgmg, a dataset directory which contains multidimensional Smolyak sparse grids based on a mixed set of 1D factor rules and a choice of growth rules.
sgmga, a C++ code which creates sparse grids based on a mixture of 1D quadrature rules, allowing anisotropic weights for each dimension.
smolpack, a C code 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_mixed, a C++ code which creates sparse grids based on a mix of 1D rules.
toms847, a MATLAB code which uses sparse grids to carry out multilinear hierarchical interpolation. It is commonly known as SPINTERP, and is by Andreas Klimke.