Sparse grids for UQ

Fred Boehm
Qian Group Meeting
February 7, 2014

Overview

numerical discretization technique for multivariate problems
constructs a multi-dimensional, multi-level basis by a special truncation of tensor product expansion of a one-dimensional multi-level basis
requires \( O(N(\log N)^{d-1}) \) degrees of freedom
- \( N \) is df in each dimension; \( d \) is dimension
compare with full tensor product & \( O(N^d) \)
reduce the impact of the 'curse of dimensionality'

one approach uses hierarchical 'hat functions'
\[ \phi(x) = 1-|x| \] for \( |x| \le 1 \)
Consider a set of equidistant grids on \( [0,1] \) with mesh width (ie, interval width) \( h_l = 2^{-l} \)
Grid points then are: \[ x_{l,i} = ih_l \] for \( 1\le i\le 2^l \)
Dilate and translate with hat function to get basis functions: \[ \phi_{l,i}(x) = \phi(\frac{x-ih_l}{h_l}) \]
With basis functions \( \phi_{l,i} \), define function space of piecewise linear functions:

\[ V_l = \text{span}\lbrace \phi_{l,i}: 1\le i \le 2^l - 1\rbrace \]

Define hierarchical increment spaces: \[ W_l = \text{span}\lbrace \phi_{l,i} : i \in I_l\rbrace \] where \( I_l = \lbrace i \in \mathbb{N} : 1 \le i \le 2^l - 1, i \text{ odd}\rbrace \)
Increment spaces satisfy:

\[ V_l = \oplus_{k \le l}W_k \]

an approximation of the definite integral of a function
usually written as a weighted sum of function evaluations at points within the domain

for univariate integral, Gaussian quadrature provides an alternative to simulation
depends on the choices of \( x \) values
for polynomials up to a certain degree, we get an exact solution

\( V = \lbrace V_i : i \in \mathbb{N}\rbrace \), a set of (univariate) quadrature rules
polynomial exactness increases as \( i \) increases
each rule \( V_i \) specifies:
- a set of \( R_i \) nodes \( \mathbb{X}_i = [x_1, x_2, ..., x_R] \)
- a weight function \( w: \mathbb{X}_i \to \mathbb{R} \)
for a function \( g \), \[ V_i[g] = \sum_{x \in \mathbb{X}_i} g(x)w_i(x) \]
Once we have nodes & weights, merely take a weigthed sum of function evaluations

For a fixed dimension of integral, sets of nodes (for rules \( V_i \)) are nested
- \( \mathbb{X}_i \subseteq \mathbb{X}_j \) if \( i < j \)
Gaussian quadrature rules are not nested; they choose optimal nodes without considering nesting
Kronrod- Patterson rules are nested sequences of univariate rules
- generally require more nodes than Gaussian, since KP requires nesting