SPARSE_GRID_OPEN_DATASET
Sparse Grid from Open 1D Quadrature Rule
SPARSE_GRID_OPEN_DATASET
is a C++ program which
computes a sparse quadrature rule for
an arbitrary spatial dimension, associated with a particular
"level" of the Smolyak construction,
and based on an open 1D quadrature rule.
The program offers a choice of open 1D quadrature rules to be used:

2: F2, the Fejer type 2 rule;

3: GP, the GaussPatterson rule;

4: NCO, the NewtonCotes Open rule;

5: TS, the TanhSinh rule;
Usage:
sparse_grid_open_dataset dim_num level_max rule
where

dim_num is the spatial dimension;

level_max is the level of the Smolyak construction;

rule is the index (2/3/4/5) of the 1D quadrature rule to use.
Licensing:
The code described and made available on this web page is distributed
under the
GNU LGPL license.
Languages:
SPARSE_GRID_OPEN_DATASET is available in
a C++ version and
a FORTRAN90 version and
a MATLAB version.
Related Data and Programs:
CC_DISPLAY,
a MATLAB library which
can compute and display Clenshaw Curtis grids in two dimensions,
as well as sparse grids formed from sums of Clenshaw Curtis grids.
QUADRATURE_RULES,
a dataset directory which
defines quadrature rules;
a number of examples of sparse grid quadrature rules are included.
QUADRULE,
a C++ library which
defines quadrature rules for
various intervals and weight functions.
SGMGA,
a C++ library which
creates sparse grids based on a mixture of 1D quadrature rules,
allowing anisotropic weights for each dimension.
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.
SPARSE_GRID_CC_DATASET,
a C++ program which
creates a sparse grid dataset based on ClenshawCurtis rules.
SPARSE_GRID_CLOSED_DATASET,
a C++ program which
creates a sparse grid dataset based on
closed rules (ClenshawCurtis, NewtonCotesClosed).
SPARSE_GRID_DISPLAY,
a MATLAB library which
can display a 2D or 3D sparse grid.
SPARSE_GRID_F2,
a dataset directory which
contains sparse
grids based on a Fejer Type 2 rule.
SPARSE_GRID_GL_DATASET,
a C++ program which
creates a sparse grid dataset based on GaussLegendre rules.
SPARSE_GRID_HERMITE_DATASET,
a C++ program which
creates a sparse grid dataset based on GaussHermite rules.
SPARSE_GRID_LAGUERRE_DATASET,
a C++ program which
creates a sparse grid dataset based on GaussLaguerrre rules.
SPARSE_GRID_MIXED,
a C++ library which
constructs a sparse grid using different rules in each spatial dimension.
SPARSE_GRID_MIXED_DATASET,
a C++ program which
creates a sparse grid dataset based on a mixture of 1D rules.
SPARSE_GRID_MIXED_GROWTH,
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.
SPARSE_GRID_NCC,
a dataset directory which
contains sparse
grids based on a Newton Cotes closed rule.
SPARSE_GRID_NCO,
a dataset directory which
contains sparse
grids based on a Newton Cotes open rule.
SPARSE_GRID_OPEN,
a C++ library which
defines define sparse grids based on open nested quadrature 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:

Volker Barthelmann, Erich Novak, Klaus Ritter,
High Dimensional Polynomial Interpolation on Sparse Grids,
Advances in Computational Mathematics,
Volume 12, Number 4, 2000, pages 273288.

Philip Davis, Philip Rabinowitz,
Methods of Numerical Integration,
Second Edition,
Dover, 2007,
ISBN: 0486453391,
LC: QA299.3.D28.

Walter Gautschi,
Numerical Quadrature in the Presence of a Singularity,
SIAM Journal on Numerical Analysis,
Volume 4, Number 3, 1967, pages 357362.

Thomas Gerstner, Michael Griebel,
Numerical Integration Using Sparse Grids,
Numerical Algorithms,
Volume 18, Number 34, 1998, pages 209232.

Prem Kythe, Michael Schaeferkotter,
Handbook of Computational Methods for Integration,
Chapman and Hall, 2004,
ISBN: 1584884282,
LC: QA299.3.K98.

Albert Nijenhuis, Herbert Wilf,
Combinatorial Algorithms for Computers and Calculators,
Second Edition,
Academic Press, 1978,
ISBN: 0125192606,
LC: QA164.N54.

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

Thomas Patterson,
The Optimal Addition of Points to Quadrature Formulae,
Mathematics of Computation,
Volume 22, Number 104, October 1968, pages 847856.

Sergey Smolyak,
Quadrature and Interpolation Formulas for Tensor Products of
Certain Classes of Functions,
Doklady Akademii Nauk SSSR,
Volume 4, 1963, pages 240243.

Dennis Stanton, Dennis White,
Constructive Combinatorics,
Springer, 1986,
ISBN: 0387963472,
LC: QA164.S79.
Source Code:
Examples and Tests:
F2_D2_LEVEL2 is an example computation based on a Fejer type 2 rule
in two dimensions and level 2.
GP_D2_LEVEL2 is an example computation based on a GaussPatterson
rule in two dimensions and level 2.
NCO_D2_LEVEL2 is an example computation based on a
NewtonCotes Open rule in two dimensions and level 2.
TS_D2_LEVEL4 is an example computation based on a
tanhsinh rule in two dimensions and level 4.
List of Routines:

MAIN is the main program for SPARSE_GRID_OPEN_DATASET.

ABSCISSA_LEVEL_OPEN_ND: first level at which given abscissa is generated.

CHOOSE computes the binomial coefficient C(N,K).

COMP_NEXT computes the compositions of the integer N into K parts.

F2_ABSCISSA returns the Ith abscissa for the Fejer type 2 rule.

F2_WEIGHTS computes weights for a Fejer type 2 rule.

GP_ABSCISSA returns the Ith abscissa for a GaussPatterson rule.

GP_WEIGHTS sets weights for a GaussPatterson rule.

I4_MAX returns the maximum of two I4's.

I4_MIN returns the smaller of two I4's.

I4_MODP returns the nonnegative remainder of I4 division.

I4_POWER returns the value of I^J.

I4MAT_TRANSPOSE_PRINT_SOME prints some of an I4MAT, transposed.

I4_TO_STRING converts an I4 to a C++ string.

I4VEC_PRODUCT multiplies the entries of an I4VEC.

INDEX_TO_LEVEL_OPEN determines the level of a point given its index.

LEVEL_TO_ORDER_OPEN converts a level to an order for open rules.

MULTIGRID_INDEX1 returns an indexed multidimensional grid.

MULTIGRID_SCALE_OPEN renumbers a grid as a subgrid on a higher level.

NCO_ABSCISSA returns the Ith abscissa for the Newton Cotes open rule.

NCO_WEIGHTS computes weights for a NewtonCotes Open rule.

PRODUCT_WEIGHTS_OPEN: weights for an open product rule.

R8_EPSILON returns the R8 roundoff unit.

R8_HUGE returns a "huge" R8.

R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.

R8MAT_WRITE writes an R8MAT file.

R8VEC_COPY copies an R8VEC.

R8VEC_DIRECT_PRODUCT2 creates a direct product of R8VEC's.

R8VEC_PRINT_SOME prints "some" of an R8VEC.

R8VEC_SUM returns the sum of an R8VEC.

S_LEN_TRIM returns the length of a string to the last nonblank.

SPARSE_GRID_OFN_SIZE sizes a sparse grid using Open Fully Nested rules.

LEVELS_OPEN_INDEX computes open grids with 0 <= LEVEL <= LEVEL_MAX.

SPGRID_OPEN_WEIGHTS gathers the weights.

TIMESTAMP prints the current YMDHMS date as a time stamp.

TS_ABSCISSA returns the Ith abscissa for the tanhsinh rule.

TS_WEIGHTS computes weights for a tanhsinh rule.

VEC_COLEX_NEXT2 generates vectors in colex order.
You can go up one level to
the C++ source codes.
Last revised on 23 December 2009.