smolyak_display, an Octave code which displays the exactness diagram for a 2D Smolyak sparse grid, by displaying and summing the exactness diagrams for the component product rules.
The exactness diagram is a plot of the monomials x^i y^j which are exactly integrated by the sparse grid. The sparse grid "inherits" its exactness from the product rules that compose it, and the program shows how this is done.
In 1D, a quadrature rule Q() is a list of N points X and weights W which approximates an integral I(f) over some region by
I(f) is approximated by Q(f) = sum ( 1 <= i <= n ) w(i) * f(x(i))
In 2D (or higher), a product quadrature rule is the most common method for estimating integrals in this way. A product rule in 2D is formed by taking two rules for 1D quadrature, say Q1 and Q2, and forming the rule Q = Q1 x Q2. Here, the points of the rule Q are formed by taking all possible pairs (x1,x2), with weights w1*w2.
A Smolyak sparse grid is generally used to form a quadrature rule Q(f) to approximate the integral I(f) of a multivariate function f(x) over a domain that is a product region. Although Smolyak grids are related to product rules, they generally are able to produce accurate estimates at a much lower "cost", that is, with a much smaller number of points N.
Typically, for a given spatial dimension D, Smolyak sparse grids are available in a sequence of sizes called "levels". Level 0 is a single point rule, and subsequent levels add more points and more accurate integral estimates.
In 2D, a Smolyak grid is a combination created by adding together product rules of a given product level, and subtracting product rules of the previous level.
One way to analyze the behavior of a sequence of sparse grids is to investigate their exactness.
A quadrature rule is exact for an integrand f(x) if it is true that Q(f)=I(f). Typically, for a 1D quadrature rule, we are interested in the exactness for monomials of the form x^j, and a quadrature rule has exactness up to degree k if it is exact for all monomials from x^0 through x^k. This immediately implies that the quadrature rule will be exact for any polynomial of degree k or less, and hence is strong information about the approximation ability of the rule.
An exactness diagram for a quadrature rule can be made, which displays all the monomials which the rule can integrate exactly. Since we are considering a Smolyak sparse grid, we can display the evolution of the exactness diagram, as we add or subtract each component product grid to the sparse grid. The program draws a black diagonal line to mark the total degree exactness of the sparse grid. It shows in dark blue the monomials which can be exactly integrated by the rule, and which lie below the exactness line. Light blue is used for monomials that can be integrated exactly, but which lie above the exactness line; these represent, in some sense, superfluous accuracy. Until the sparse grid is completely constructed, some monomials under the exactness line may actually be incorrectly estimated at double, or triple, or minus their true value. This is suggested by using other colors for such monomials. However, once the sparse grid is complete, the entire field of monomials below the diagonal line should be dark blue.
Two "families" of quadrature rules are available:
The Clenshaw-Curtis family is defined on [-1,+1]. Roughly speaking, the rule with N points has exactness N-1. Actually, because of symmetric, if N is odd, then the rule with N points will actually have exactness N. In particular, the rule with 1 point has exactness 1, and can integrate both constants (degree 0) and linear functions (degree 1) exactly.
The Legendre family is defined on [-1,+1]. The rule with N points has exactness 2*N-1.
While the families can produce rules of any size, we wish to select a subsequence of these rules, which increase in size to satisfy some pattern we specify. This pattern is called the "growth rate". A common growth rate is "exponential", in which the number of points roughly doubles on each step. For technical reasons, the Clenshaw-Curtis and Legendre families differ in how they grow exponentially. Other simple growth rules include "slow exponential", "linear", and "linear odd".
The "hyperbolic cross" growth rule is quite different from the others. Essentially, when we specify a level L, the 2D product rules that we will be combining for the hyperbolic cross involve sizes L1 and L2 whose product is L (or close to it). Thus, the hyperbolic cross grid of level 5 adds: +Q(1)xQ(6) + Q(2)xQ(3) + Q(3)xQ(2) + Q(6)xQ(1) and subtracts: -Q(1)xQ(3)-Q(2)xQ(2)-Q(3)xQ(1). This growth rule is appropriate for integrand functions which are biases towards pure powers of a single variable (x or y in our case) and against powers that involve both x and y.
smolyak_display ( 'family', 'growth', level )where
Choices for 'family' include:
Choices for 'growth' include:
The information on this web page is distributed under the MIT license.
smolyak_display is available in a MATLAB version and an Octave version.
sparse_grid_hw, an Octave code 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.
spinterp, an Octave code which carries out piecewise multilinear hierarchical sparse grid interpolation, quadrature and optimization, by Andreas Klimke; an earlier version of this software is ACM TOMS Algorithm 847.