SGMGA
Sparse Grid Mixed Growth Anisotropic Rules.

SGMGA is a C++ library which implements a family of sparse grid rules. These rules are "mixed", in that a different 1D quadrature rule can be specified for each dimension. Moreover, each 1D quadrature rule comes in a family of increasing size whose growth rate (typically linear or exponential) is chosen by the user. Finally, the user may also specify different weights for each dimension, resulting in anisotropic rules.

SGMGA calls many routines from the SANDIA_RULES library. Source code or compiled copies of both libraries must be available when a program wishes to use the SGMGA library.

Thanks to Drew Kouri, who pointed out a discrepancy in the computation of the variable level_1d_max which meant that certain sparse grids requested the generation of a 1D rule of a level that was higher than necessary by 1. In particular, if the Gauss-Patterson rule was involved, sparse grids that actually only needed rules of level 7 would ask also for level 8, resulting in the computation being terminated. This problem was corrected on 25 April 2011.

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	Default	"DF", moderate exponential or moderate linear
1	"SL", Slow linear	O=L+1
2	"SO", Slow Linear Odd	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.

Web Link:

A version of the sparse grid library is available in http://tasmanian.ornl.gov, the TASMANIAN library, available from Oak Ridge National Laboratory.

Licensing:

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

Languages:

SGMGA is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

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

QUADRULE, 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_SGMGA, a C++ library which creates sparse grids based on a mixture of 1D quadrature rules, allowing anisotropic weights for each dimension. This is a version of SGMGA that uses a different procedure for supplying the parameters needed to evaluate certain quadrature rules.

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

SGMG, a C++ library 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.

SGMGA, a dataset directory which contains SGMGA files (Sparse Grid Mixed Growth Anisotropic), that is, multidimensional Smolyak sparse grids based on a mixture of 1D rules, and with a choice of exponential and linear growth rates for the 1D rules and anisotropic weights for the dimensions.

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_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.

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

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.

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. Michael Eldred, John Burkardt,
   Comparison of Non-Intrusive Polynomial Chaos and Stochastic Collocation Methods for Uncertainty Quantification,
   American Institute of Aeronautics and Astronautics,
   Paper 2009-0976,
   47th AIAA Aerospace Sciences Meeting Including The New Horizons Forum and Aerospace Exposition,
   5 - 8 January 2009, Orlando, Florida.
5. Walter Gautschi,
   Numerical Quadrature in the Presence of a Singularity,
   SIAM Journal on Numerical Analysis,
   Volume 4, Number 3, September 1967, pages 357-362.
6. Thomas Gerstner, Michael Griebel,
   Numerical Integration Using Sparse Grids,
   Numerical Algorithms,
   Volume 18, Number 3-4, 1998, pages 209-232.
7. Gene Golub, John Welsch,
   Calculation of Gaussian Quadrature Rules,
   Mathematics of Computation,
   Volume 23, Number 106, April 1969, pages 221-230.
8. Prem Kythe, Michael Schaeferkotter,
   Handbook of Computational Methods for Integration,
   Chapman and Hall, 2004,
   ISBN: 1-58488-428-2,
   LC: QA299.3.K98.
9. Albert Nijenhuis, Herbert Wilf,
   Combinatorial Algorithms for Computers and Calculators,
   Second Edition,
   Academic Press, 1978,
   ISBN: 0-12-519260-6,
   LC: QA164.N54.
10. Fabio Nobile, Raul Tempone, Clayton Webster,
    A Sparse Grid Stochastic Collocation Method for Partial Differential Equations with Random Input Data,
    SIAM Journal on Numerical Analysis,
    Volume 46, Number 5, 2008, pages 2309-2345.
11. Fabio Nobile, Raul Tempone, Clayton Webster,
    An Anisotropic Sparse Grid Stochastic Collocation Method for Partial Differential Equations with Random Input Data,
    SIAM Journal on Numerical Analysis,
    Volume 46, Number 5, 2008, pages 2411-2442.
12. Thomas Patterson,
    The Optimal Addition of Points to Quadrature Formulae,
    Mathematics of Computation,
    Volume 22, Number 104, October 1968, pages 847-856.
13. 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.
14. Sergey Smolyak,
    Quadrature and Interpolation Formulas for Tensor Products of Certain Classes of Functions,
    Doklady Akademii Nauk SSSR,
    Volume 4, 1963, pages 240-243.
15. Arthur Stroud, Don Secrest,
    Gaussian Quadrature Formulas,
    Prentice Hall, 1966,
    LC: QA299.4G3S7.
16. 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:

• sgmga.cpp, the source code.
• sgmga.hpp, the include file.

Examples and Tests:

SGMGA_ANISO_NORMALIZE_test tests SGMGA_ANISO_BALANCE, SGMGA_ANISO_NORMALIZE and SGMGA_IMPORTANCE_TO_ANISO.

• sgmga_aniso_normalize_test.cpp, the program.
• sgmga_aniso_normalize_test.txt, the output file.

SGMGA_INDEX_test tests SGMGA_INDEX.

• sgmga_index_test.cpp, the program.
• sgmga_index_test.txt, the output file.

SGMGA_POINT_test tests SGMGA_POINT.

• sgmga_point_test.cpp, the program.
• sgmga_point_test.txt, the output file.

SGMGA_PRODUCT_WEIGHT_test tests SGMGA_PRODUCT_WEIGHT.

• sgmga_product_weight_test.cpp, the program.
• sgmga_product_weight_test.txt, the output file.

SGMGA_SIZE_test tests SGMGA_SIZE and SGMGA_SIZE_TOTAL.

• sgmga_size_test.cpp, the program.
• sgmga_size_test.txt, the output file.

SGMGA_SIZE_TABLE tabulates the point counts from SGMGA_SIZE for an isotropic rule over a range of dimensions and levels.

• sgmga_size_table.cpp, the program.
• sgmga_size_table_output.txt, the output file.

SGMGA_UNIQUE_INDEX_test tests SGMGA_UNIQUE_INDEX.

• sgmga_unique_index_test.cpp, the program.
• sgmgav_index_test.txt, the output file.

SGMGA_VCN_test tests SGMGA_VCN and SGMGA_VCN_ORDERED.

• sgmga_vcn_test.cpp, the program.
• sgmga_vcn_test.txt, the output file.

SGMGA_VCN_COEF_test tests SGMGA_VCN_COEF.

• sgmga_vcn_coef_test.cpp, the program.
• sgmga_vcn_coef_test.txt, the output file.

SGMGA_WEIGHT_test tests SGMGA_WEIGHT.

• sgmga_weight_test.cpp, the program.
• sgmga_weight_test.txt, the output file.

SGMGA_WRITE_test tests SGMGA_WRITE.

• sgmga_write_test.cpp, the program.
• sgmga_write_test.txt, the output file.

List of Routines:

• SGMGA_ANISO_BALANCE "balances" an anisotropic weight vector.
• SGMGA_ANISO_NORMALIZE normalizes the SGMGA anisotropic weight vector.
• SGMGA_IMPORTANCE_TO_ANISO: importance vector to anisotropic weight vector.
• SGMGA_INDEX indexes an SGMGA grid.
• SGMGA_POINT computes the points of an SGMGA rule.
• SGMGA_PRODUCT_WEIGHT computes the weights of a mixed product rule.
• SGMGA_SIZE sizes an SGMGA grid, discounting duplicates.
• SGMGA_SIZE_TOTAL sizes an SGMGA grid, counting duplicates.
• SGMGA_UNIQUE_INDEX maps nonunique to unique points.
• SGMGA_VCN returns the next constrained vector.
• SGMGA_VCN_COEF returns the "next" constrained vector's coefficient.
• SGMGA_VCN_COEF_NAIVE returns the "next" constrained vector's coefficient.
• SGMGA_VCN_NAIVE returns the next constrained vector.
• SGMGA_VCN_ORDERED returns the "next" constrained vector, with ordering.
• SGMGA_VCN_ORDERED_NAIVE returns the "next" constrained vector, with ordering.
• SGMGA_WEIGHT computes weights for an SGMGA grid.
• SGMGA_WRITE writes an SGMGA rule to six files.

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