Sparse grid cubature and mixed regularity

Let $Q:\{g:[0,1]\to \mathbb{R}\}\to \mathbb{R}$ be a finite quadrature functional of the form $Q(g)={\sum }_{i=1}^m{w}_{i}g(x_i),$ where $m\ge 1$, the nodes $x_i\in [0,1]$ are distinct, and $w_i\in \mathbb{R}$. A one-dimensional nested level hierarchy is a sequence $(Q_{\mathrm{\ell }}{)}_{\mathrm{\ell }\in {\mathbb{N}}_0}$ of such functionals, with node sets $X_{\mathrm{\ell }}=\{x_{\mathrm{\ell },i}:1\le i\le m_{\mathrm{\ell }}\}$ satisfying $X_{\mathrm{\ell }-1}\subseteq X_{\mathrm{\ell }}$ for every $\mathrm{\ell }\ge 1$. Set $Q_{-1}:=0$, the zero functional, and define the detail functional ${\mathrm{\Delta }}_0:=Q_0,{\mathrm{\Delta }}_{\mathrm{\ell }}:=Q_{\mathrm{\ell }}-Q_{\mathrm{\ell }-1}(\mathrm{\ell }\ge 1)\mathrm{.}$ Finite sums are as in Finite sums and finite products, by recursion. For each $d\ge 1$, the integration functional used below is $I_d(f):={\int }_{[0,1{]}^d}f$, with the multiple Riemann integral convention of The lower and upper Darboux integrals over a nondegenerate rectangle in ${\mathbb{R}}^m$.

The convergence and rate results in this pair use the dyadic composite- Simpson hierarchy $Q_{\mathrm{\ell }}(g):=Q_S(g;0,1,2^{\mathrm{\ell }+1}),X_{\mathrm{\ell }}=\{k\mathrm{/}{2}^{\mathrm{\ell }+1}:0\le k\le 2^{\mathrm{\ell }+1}\},$ where $Q_S$ is the even-panel rule of Composite Simpson rule on an even uniform grid. The number of panels is even and at least two. The sets are nested because $k\mathrm{/}{2}^{\mathrm{\ell }}=2k\mathrm{/}{2}^{\mathrm{\ell }+1}$, and their weights are nonnegative with total weight one: each two-panel block has nonnegative weights $H(1,4,1)\mathrm{/}6$ summing to its length $H$, and the blocks partition an interval of length one. Level zero has nodes $0,1\mathrm{/}2,1$ and weights $1\mathrm{/}6,4\mathrm{/}6,1\mathrm{/}6$.

For a multi-index $\mathrm{\ell }=({\mathrm{\ell }}_1,\dots ,{\mathrm{\ell }}_d)\in {\mathbb{N}}_0^d$, any tensor product $R_{{\mathrm{\ell }}_1}^{(1)}\otimes \cdots \otimes R_{{\mathrm{\ell }}_d}^{(d)}$ of these finite functionals means the finite weighted functional obtained by multiplying the coordinate weights and evaluating on the corresponding node tuples. In particular, ${\mathrm{\Delta }}_{\mathrm{\ell }}:={\mathrm{\Delta }}_{{\mathrm{\ell }}_1}^{(1)}\otimes \cdots \otimes {\mathrm{\Delta }}_{{\mathrm{\ell }}_d}^{(d)}$. No exactness or error property is implied by the notation alone.

Fix a dimension $d\ge 1$. A finite set $\mathrm{\Lambda }\subseteq {\mathbb{N}}_0^d$ is downward closed if, whenever $\mathrm{\ell }\in \mathrm{\Lambda }$ and ${\mathrm{\ell }}_j>0$, the index $\mathrm{\ell }-e_j$ also belongs to $\mathrm{\Lambda }$; here $e_j$ is the $j$th coordinate unit vector. In this pair an admissible Smolyak set is a nonempty finite downward- closed $\mathrm{\Lambda }$ that contains $0$.

For a level hierarchy from Nested one-dimensional quadrature levels and differences, define the scalar detail value ${\delta }_{\mathrm{\ell }}(f):=({\mathrm{\Delta }}_{{\mathrm{\ell }}_1}^{(1)}\otimes \cdots \otimes {\mathrm{\Delta }}_{{\mathrm{\ell }}_d}^{(d)})(f),$ and the Smolyak cubature functional $Q_{\mathrm{\Lambda }}(f):={\sum }_{\mathrm{\ell }\in \mathrm{\Lambda }}{\delta }_{\mathrm{\ell }}(f)\mathrm{.}$ Each summand is a finite signed weighted sum. Expanding all differences and adding coefficients at equal points gives one finite signed weight for each distinct node in ${\mathcal{N}}_{\mathrm{\Lambda }}:={\bigcup }_{\mathrm{\ell }\in \mathrm{\Lambda }}{X}_{{\mathrm{\ell }}_1}\times \cdots \times X_{{\mathrm{\ell }}_d}\mathrm{.}$ The node-union work count for this direct evaluation convention is $W(\mathrm{\Lambda }):=\mathrm{\mid }{\mathcal{N}}_{\mathrm{\Lambda }}\mathrm{\mid }$, so shared nodes are counted once. A combined weight may be negative or zero; no positivity claim follows from the definition.

Let $d\ge 1$ and let $f:[0,1{]}^d\to \mathbb{R}$ be continuous. For the dyadic composite-Simpson hierarchy of Nested one-dimensional quadrature levels and differences, the tensor product $Q_L^{\otimes d}$ converges to the multiple Riemann integral: ${\lim }_{L\to \mathrm{\infty }}{Q}_L^{\otimes d}(f)=I_d(f)\mathrm{.}$

Input: dimension $d\ge 1$, a finite downward-closed $\mathrm{\Lambda }\subseteq {\mathbb{N}}_0^d$ containing $0$, the finitely many levels required by $\mathrm{\Lambda }$, a function $f$ evaluable at their nodes, and for each exact node a canonical key in a totally ordered set. Keys must agree exactly if and only if the real node tuples agree. If any required rule or key is missing, return invalid-input.

Output: the sorted list of distinct node tuples with their combined signed weights, the value $Q_{\mathrm{\Lambda }}(f)$, and the actual evaluation count $W(\mathrm{\Lambda })$.

1. Expand each detail ${\mathrm{\Delta }}_{\mathrm{\ell }}$ in the finite Smolyak sum of Smolyak cubature on a finite downward-closed index set by replacing each coordinate factor ${\mathrm{\Delta }}_0$ with $Q_0$ and each ${\mathrm{\Delta }}_r$ ($r\ge 1$) with $Q_r-Q_{r-1}$. Enumerate the resulting finite signed tensor rules in lexicographic multi-index order.
2. For each tensor rule, enumerate its finite node tuples in lexicographic coordinate-key order. Add its signed coefficient to a finite map indexed by the exact tuple key; initialize an unseen key with coefficient $0$.
3. Form ${\mathcal{N}}_{\mathrm{\Lambda }}={\bigcup }_{\mathrm{\ell }\in \mathrm{\Lambda }}{X}_{{\mathrm{\ell }}_1}\times \cdots \times X_{{\mathrm{\ell }}_d}$, sort its distinct exact keys, and evaluate $f$ once at each of these keys. Return the map of combined coefficients and the finite sum of coefficient times function value. Set $W(\mathrm{\Lambda }):=\mathrm{\mid }{\mathcal{N}}_{\mathrm{\Lambda }}\mathrm{\mid }$, including any node whose combined coefficient is zero; this is the work convention used in this pair.

This is an exact-real finite procedure. Approximate floating-point node comparisons, arithmetic, and function-evaluation error are outside its claims.

Let $A\subseteq {\mathbb{N}}_0^d$ and let $a_{\mathrm{\ell }}\ge 0$ for $\mathrm{\ell }\in A$. The nonnegative sum ${\sum }_{\mathrm{\ell }\in A}{a}_{\mathrm{\ell }}$ is defined when the set $\{{\sum }_{\mathrm{\ell }\in F}{a}_{\mathrm{\ell }}:F\subseteq A\text{ finite}\}$ is bounded above; its value is the supremum of that set in the complete ordered field $\mathbb{R}$ (Complete ordered field (least-upper-bound property)). The empty finite sum is $0$. This definition does not require an enumeration of $A$.

For the Smolyak details ${\delta }_{\mathrm{\ell }}(f)$ of Smolyak cubature on a finite downward-closed index set, absolute detail summability means that ${\sum }_{\mathrm{\ell }\in A}\mathrm{\mid }{\delta }_{\mathrm{\ell }}(f)\mathrm{\mid }$ is defined for $A={\mathbb{N}}_0^d$. For an omitted set $A={\mathbb{N}}_0^d\setminus \mathrm{\Lambda }$, the same definition gives the omitted absolute-detail tail.

Use the dyadic composite-Simpson hierarchy of Nested one-dimensional quadrature levels and differences. Let $d\ge 1$. For $S=\{j_1<\cdots <j_k\}\subseteq \{1,\dots ,d\}$, define $D_{S}f:={\mathrm{\partial }}_{x_{j_k}}^4\cdots {\mathrm{\partial }}_{x_{j_1}}^{4}f,$ so these derivatives are applied in increasing coordinate order; set $D_{\mathrm{\varnothing }}f=f$. Assume every $D_{S}f$ is continuous on the closed cube, with the one-sided endpoint convention of Higher derivatives and the classes $C^k$ and $C^{\mathrm{\infty }}$, and choose finite bounds $M_S\ge 0$ such that $\mathrm{\mid }{D}_{S}f(x)\mathrm{\mid }\le M_S$ on $[0,1{]}^d$. For $\mathrm{\ell }\in {\mathbb{N}}_0^d$, put $S(\mathrm{\ell }):=\{j:{\mathrm{\ell }}_j\ge 1\}$ and ${\delta }_{\mathrm{\ell }}(f):=({\mathrm{\Delta }}_{{\mathrm{\ell }}_1}^{(1)}\otimes \cdots \otimes {\mathrm{\Delta }}_{{\mathrm{\ell }}_d}^{(d)})(f)\mathrm{.}$ Then $\mathrm{\mid }{\delta }_{\mathrm{\ell }}(f)\mathrm{\mid }\le M_{S(\mathrm{\ell })}{\left(\frac{17}{2880}\right)}^{\mathrm{\mid }S(\mathrm{\ell })\mathrm{\mid }}{16}^{-{\sum }_{j\in S(\mathrm{\ell })}{\mathrm{\ell }}_j}\mathrm{.}$ Moreover, for every finite $F\subseteq {\mathbb{N}}_0^d$, ${\sum }_{\mathrm{\ell }\in F}\mathrm{\mid }{\delta }_{\mathrm{\ell }}(f)\mathrm{\mid }\le {\sum }_{S\subseteq \{1,\dots ,d\}}{M}_S{\left(\frac{17}{43200}\right)}^{\mathrm{\mid }S\mathrm{\mid }}<\mathrm{\infty }\mathrm{.}$

Let $d\ge 1$ and $m=(m_1,\dots ,m_d)\in {\mathbb{N}}_0^d$. For $R_m:=\{\mathrm{\ell }\in {\mathbb{N}}_0^d:0\le {\mathrm{\ell }}_j\le m_j\text{ for every }j\}$ and the details of Nested one-dimensional quadrature levels and differences, ${\sum }_{\mathrm{\ell }\in R_m}{\mathrm{\Delta }}_{\mathrm{\ell }}=Q_{m_1}^{(1)}\otimes \cdots \otimes Q_{m_d}^{(d)}\mathrm{.}$

Input: dimension $d\ge 1$; a finite downward-closed cap $\mathrm{\Gamma }\subseteq {\mathbb{N}}_0^d$ containing $0$; for each coordinate, the one-dimensional quadrature rules from a hierarchy as in Nested one-dimensional quadrature levels and differences through every level used by $\mathrm{\Gamma }$, with canonical node keys that agree exactly if and only if the real nodes agree and are totally ordered; a function $f$ evaluable at the nodes; and an integer evaluation budget $B\ge 0$. Admissible inputs supply all these rules and keys at every level required by $\mathrm{\Gamma }$.

Output: a current downward-closed index set $\mathrm{\Lambda }\subseteq \mathrm{\Gamma }$, its Smolyak value when the initial rule fits the budget, the computed detail surpluses, the distinct nodes actually sampled, and one status: budget-too-small, budget-exhausted, or frontier-exhausted.

1. An index $\mathrm{\ell }\in \mathrm{\Gamma }\setminus \mathrm{\Lambda }$ is admissible when every immediate predecessor $\mathrm{\ell }-e_j$ with ${\mathrm{\ell }}_j>0$ already belongs to $\mathrm{\Lambda }$. Its surplus is the exact detail value ${\delta }_{\mathrm{\ell }}(f)$ and its selection indicator is $\mathrm{\mid }{\delta }_{\mathrm{\ell }}(f)\mathrm{\mid }$.
2. Form the baseline node set $X_0^d$. If its cardinality exceeds $B$, return budget-too-small, an empty $\mathrm{\Lambda }$, no cubature value, and no sampled nodes. Otherwise set $\mathrm{\Lambda }:=\{0\}$, initialize the active candidate set as empty, evaluate $f$ once at every baseline node, and set the current value to $Q_{\{0\}}(f)$. Then process every initially admissible index in $\mathrm{\Gamma }\setminus \mathrm{\Lambda }$ in lexicographic order using step 3.
3. Visit newly admissible indices in lexicographic order, skipping any index already recorded as active, accepted, or uncomputed-budget. To compute one surplus, form its finite tensor-detail node set and the new keys not already sampled. If adding them would exceed $B$, record this candidate as uncomputed-budget without evaluating those nodes. Otherwise evaluate each new key once, store the values, compute ${\delta }_{\mathrm{\ell }}(f)$ from the finite signed weights, and add the index to the active candidate set.
4. If the active set is empty and an admissible uncomputed-budget candidate remains, return budget-exhausted. Otherwise, if the active set is empty, return frontier-exhausted.
5. Otherwise select the active index with largest absolute surplus, breaking ties lexicographically. Remove it from the active set, mark it accepted, add it to $\mathrm{\Lambda }$, update the cubature value by adding its signed surplus, and inspect its finite forward neighbors for newly admissible indices; process them by step 3. Repeat from step 4.

The evaluation budget counts the union of distinct keys sampled while computing both accepted and candidate surpluses. The indicator $\mathrm{\mid }{\delta }_{\mathrm{\ell }}(f)\mathrm{\mid }$ is a refinement heuristic only. A threshold on this indicator, or exhaustion of the finite candidate cap, is not an error certificate unless a separate omitted-tail bound applies.

Let $d\ge 1$, let $f:[0,1{]}^d\to \mathbb{R}$ be continuous, and use a level hierarchy as in Nested one-dimensional quadrature levels and differences. Suppose its tensor rules satisfy $Q_L^{\otimes d}(f)\to I_d(f)$ and its detail family is absolutely summable in the sense of Absolute summability of a multi-index detail family. For every finite downward-closed $\mathrm{\Lambda }\subseteq {\mathbb{N}}_0^d$ containing $0$, $\mathrm{\mid }{I}_d(f)-Q_{\mathrm{\Lambda }}(f)\mathrm{\mid }\le {\sum }_{\mathrm{\ell }\in {\mathbb{N}}_0^d\setminus \mathrm{\Lambda }}\mathrm{\mid }{\delta }_{\mathrm{\ell }}(f)\mathrm{\mid }\mathrm{.}$ In particular, the dyadic composite-Simpson hierarchy satisfies the convergence hypothesis for continuous $f$ by Convergence of dyadic tensor composite-Simpson rules, and for the mixed-derivative class of Mixed-derivative bounds for dyadic Simpson details the same hierarchy also satisfies absolute summability.

Let $d\ge 1$ and let $(Q_{\mathrm{\ell }})$ be a nested hierarchy as in Nested one-dimensional quadrature levels and differences. Suppose nondecreasing integers $r_{\mathrm{\ell }}\ge 0$ are supplied such that $Q_{\mathrm{\ell }}(p)={\int }_0^{1}p$ for every real polynomial $p$ of degree at most $r_{\mathrm{\ell }}$. Let $p_j$ be a polynomial of degree at most $s_j$ in coordinate $j$, and suppose $q_j$ is the least level with $s_j\le r_{q_j}$. If a finite downward-closed Smolyak set $\mathrm{\Lambda }$ contains the whole rectangle $R_q=\{\mathrm{\ell }:0\le {\mathrm{\ell }}_j\le q_j\}$, then its rule Smolyak cubature on a finite downward-closed index set exactly integrates every finite linear combination of the tensor polynomials $p_1(x_1)\cdots p_d(x_d)$ with those coordinate-degree bounds. In particular, for ${\mathrm{\Lambda }}_n:=\{\mathrm{\ell }\in {\mathbb{N}}_0^d:\mathrm{\mid }\mathrm{\ell }{\mathrm{\mid }}_1\le n\},$ the rule is exact whenever ${\sum }_j{q}_j\le n$. The $r_{\mathrm{\ell }}$ are the exactness degrees of the actual one-dimensional levels, distinct from the node counts $m_{\mathrm{\ell }}$ in the hierarchy definition; the conclusion does not infer exactness degrees from node counts.

For the selected composite-Simpson hierarchy, each level is exact through degree three, so every tensor polynomial with coordinate degrees at most three is exact on any admissible $\mathrm{\Lambda }$.

Let $\mathrm{\Gamma }$ be the finite downward-closed candidate cap of Finite-budget dimension-adaptive Smolyak surplus selection. The algorithm preserves a downward-closed accepted set $\mathrm{\Lambda }\subseteq \mathrm{\Gamma }$ and terminates after at most $\mathrm{\mid }\mathrm{\Gamma }\mathrm{\mid }$ accepted index additions, returning one of its declared statuses.

Use the dyadic composite-Simpson hierarchy of Nested one-dimensional quadrature levels and differences. Let $d\ge 1$, $n\ge 2d$, and let $f:[0,1{]}^d\to \mathbb{R}$ satisfy the continuous mixed fourth-derivative hypotheses and bounds $M_S$ of Mixed-derivative bounds for dyadic Simpson details. Define the isotropic index set ${\mathrm{\Lambda }}_n:=\{\mathrm{\ell }\in {\mathbb{N}}_0^d:\mathrm{\mid }\mathrm{\ell }{\mathrm{\mid }}_1\le n\},$ and let $W_{n,d}:=\mathrm{\mid }{\mathcal{N}}_{{\mathrm{\Lambda }}_n}\mathrm{\mid }$ be the distinct-node work count of Smolyak cubature on a finite downward-closed index set and Deterministic node merging for Smolyak cubature. For a dyadic node $x$, let $t(x)=0$ for $x=0,1,1\mathrm{/}2$; if $x=p\mathrm{/}{2}^{r+1}$ is interior and reduced with odd numerator $p$, let $t(x)=r\ge 1$. Put $a_0:=3,a_r:=2^r(r\ge 1),$ $\mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{m}\mathrm{i}\mathrm{x},d}:={\sum }_{\mathrm{\varnothing }\mathrm{\ne }S\subseteq \{1,\dots ,d\}}{\left(\frac{17}{2880}\right)}^{\mathrm{\mid }S\mathrm{\mid }}{M}_S,T_d:={\sup }_{N\ge 1}{\sum }_{r=1}^N{r}^{d-1}{16}^{-r},$ $D_d:=2\cdot 3^d{d}^{d-1},C_d:=D_d^4{T}_d{\left(\frac{3}{\log 2}\right)}^{5(d-1)},$ where $\log$ is the natural logarithm of The natural logarithm as the inverse of the exponential function. Then $T_d<\mathrm{\infty }$, and the actual node-union count and error satisfy $W_{n,d}={\sum }_{\begin{array}{c}t\in {\mathbb{N}}_0^d\\ \mathrm{\mid }t{\mathrm{\mid }}_1\le n\end{array}}{\prod }_{j=1}^d{a}_{t_j},2^n\left(\genfrac{}{}{0px}{}{n-1}{d-1}\right)\le W_{n,d}\le D_d{2}^n(n+1{)}^{d-1},$ $\mathrm{\mid }{I}_d(f)-Q_{{\mathrm{\Lambda }}_n}(f)\mathrm{\mid }\le T_d\mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{m}\mathrm{i}\mathrm{x},d}{16}^{-n}(n+1{)}^{d-1}\le C_d\mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{m}\mathrm{i}\mathrm{x},d}{W}_{n,d}^{-4}(\log (2+W_{n,d}){)}^{5(d-1)}\mathrm{.}$ All constants and the mixed-derivative quantity display their dimension dependence; no weighted-anisotropic tractability claim is made.