Application of Quasi-Monte Carlo Methods to PDEs with Random Coefficients – An Overview and Tutorial

Abstract

This article provides a high-level overview of some recent works on the application of quasi-Monte Carlo (QMC) methods to PDEs with random coefficients. It is based on an in-depth survey of a similar title by the same authors, with an accompanying software package which is also briefly discussed here. Embedded in this article is a step-by-step tutorial of the required analysis for the setting known as the uniform case with first order QMC rules. The aim of this article is to provide an easy entry point for QMC experts wanting to start research in this direction and for PDE analysts and practitioners wanting to tap into contemporary QMC theory and methods.

1 Introduction

Uncertainty quantification is the science of quantitative characterization and reduction of uncertainties in both computational and real world applications, and it is the source of many challenging high dimensional integration and approximation problems. Often the high dimensionality comes from uncertainty or randomness in the data, e.g., in groundwater flow from permeability that is rapidly varying and uncertain, or in financial mathematics from the rapid and often unpredictable changes within markets. The input data may be a random variable or a random field, in which case the derived quantity of interest will in general also be a random variable or a random field. The computational goal is usually to find the expected value or other statistics of these derived quantities.

A popular example is the flow of water through a disordered porous medium, modeled by Darcy’s law coupled with the mass conservation law, i.e.,

$$\begin{aligned} q({\varvec{x}},\omega ) + a({\varvec{x}},\omega )\,\nabla p({\varvec{x}},\omega )&\,=\, 0\,, \\ \nabla \cdot q({\varvec{x}},\omega )&\,=\, 0\,, \end{aligned}$$

for ${\varvec{x}}$ in a bounded domain $D\subset {\mathbb {R}}^d$, $d\in \{1,2,3\}$, and for almost all events $\omega$ in the probability space $(\varOmega ,\mathscr {A},{\mathbb {P}})$. Here $q({\varvec{x}},\omega )$ is the velocity (also called the specific discharge) and $p({\varvec{x}},\omega )$ is the residual pressure, while $a({\varvec{x}},\omega )$ is the permeability (or more precisely, the ratio of permeability to dynamic viscosity) which is modelled as a random field. Uncertainty in $a({\varvec{x}},\omega )$ leads to uncertainty in $q({\varvec{x}},\omega )$ and $p({\varvec{x}},\omega )$. Quantities of interest include for example the breakthrough time of a plume of pollution moving through the medium.

QMC for PDEs with Random Coefficients

There is a huge literature on treating these PDEs with random coefficients using various methods, see e.g., the surveys [1, 23, 43] and the references therein. Here we are interested in the application of quasi-Monte Carlo (QMC) methods, which are equal-weight quadrature rules for high dimensional integrals, see e.g., [3, 5, 36,37,38,39, 44].

QMC methods are still relatively new to these PDE problems. It began with the 2011 paper [21] which included comprehensive numerical experiments showing promising QMC results, but without any theoretical justification. The first fully justified theory was provided in the 2012 paper [32], and this has lead to a flood of research activities. We will follow the recent survey [31] to provide a high-level overview of how QMC theory can be applied to PDEs with random coefficients. The survey [31] covered the detailed analysis from six papers [6, 8, 22, 32,33,34] in a unified view. Different algorithms have been analyzed: single-level vs multi-level, deterministic vs randomized, and first order vs higher order, and they were considered under different models for the randomness as we explain below.

It is popular to assume that $a({\varvec{x}},\omega )$ is a lognormal random field, that is, $\log (a({\varvec{x}},\omega ))$ is a Gaussian random field on the spatial domain D with a specified mean and covariance function. Then one can use the Karhunen–Loève (KL) expansion to write $\log (a({\varvec{x}},\omega ))$ as an infinite series parametrised by a sequence $y_j = y_j(\omega )$, $j\ge 1$, of i.i.d. standard normal random numbers from ${\mathbb {R}}$. Aside from the lognormal case, often the simpler uniform case is considered, where $a({\varvec{x}},\omega )$ is written as an infinite series that depends linearly on a sequence $y_j = y_j(\omega )$, $j\ge 1$, of i.i.d. uniform random numbers from a bounded interval of $[-1,1]$ or $[-\frac{1}{2},\frac{1}{2}]$. In both the lognormal and uniform cases the infinite series is truncated in practice to, say, s terms. The expected value of any quantity of interest is then approximated by an s-dimensional integral with respect to the parameters $y_j$, which can in turn be approximated by QMC methods, combined with finite element methods for solving the PDE.

The six papers surveyed in [31] all followed this KL-based general direction. With respect to the QMC method they can be either first order or higher order, which refers to the rate of convergence being close to ${\mathscr {O}}(n^{-1})$ or ${\mathscr {O}}(n^{-\alpha })$, $\alpha >1$, with n being the number of integrand evaluations. With respect to the approximation of the integrand function they can be either single-level or multi-level, which refers to how spatial discretization and dimension truncation are performed. A summary of the results is given in the table below:

	Uniform case	Lognormal case
First order single-level analysis	[32]	[22]
First order multi-level analysis	[33]	[34]
Higher order single-level analysis	[6]
Higher order multi-level analysis	[8]

The first order results [22, 32,33,34] are based on randomly shifted lattice rules and are accompanied by probabilistic error bounds. The higher order results [6, 8] are based on interlaced polynomial lattice rules and are accompanied by deterministic error bounds. The lognormal results [22, 34] require a non-standard function space setting for integrands with domain ${\mathbb {R}}^s$. A key feature in all these analysis is that the QMC error bounds are independent of the number of integration variables s. There is as yet no satisfactory QMC theory that can give higher order convergence for the lognormal case with error bound independent of s.

Plan of this Article

In Sect. 2 we provide an overview of the different settings and algorithms covered in the survey [31], with the goal to convey the overall picture while keeping the exposition as simple and accessible as possible. In Sect. 3 we take a change of pace and style to give a step-by-step tutorial of the required analysis for the uniform case with first order QMC rules. That is, we zoom in and focus on the essence of the paper [32] in such a way that the tutorial can be used to extend the analysis to other cases by interested readers. Then in Sect. 4 we zoom out again and continue to provide insights to the key analysis required for the six papers surveyed in [31]. In Sect. 5 we briefly discuss the software accompanying [31]. Finally in Sect. 6 we give a short conclusion.

Beyond the Survey

There have been many developments beyond the scope of the survey [31].

Instead of using the KL expansion, in the lognormal case one can sample the random field only at a discrete set of points with respect to the covariance matrix inherited from the given covariance function of the continuous field. The random field is then represented exactly at these points, thus eliminating completely the truncation error associated with the KL-based approach. (Note that interpolation may be required at the finite element quadrature nodes.) The resulting large matrix factorization problem could potentially be handled by circulant embedding and FFT, if the covariance function is stationary and the grid is regular, see [10]. In fact, this was the approach taken in the first QMC paper for PDEs with random coefficients [21], and the corresponding analysis is being considered in [19, 20].

Another way to tackle the large matrix factorization is to make use of H-matrix techniques, see [24], and this has been considered in [11].

The uniform framework can be extended from the elliptic PDE to the general framework of affine parametric operator equations, see [42] as well as [6, 8]. A different QMC theory for the lognormal case is offered in [26]. Further PDE computations with higher order QMC are reported in [14], and with multi-level and multi-index QMC in [40]. QMC has also been applied to PDEs on the sphere [35], holomorphic equations [9], Bayesian inversion [4, 41], stochastic wave propagation [12, 13], and eigenproblems [16].

Moreover, there has been some significant development in the use of functions with local support in the expansions of $a({\varvec{x}},\omega )$ which leads to a simplified norm estimate for the integrand and a reduced construction cost (pre-computation) for QMC, see [15, 27, 29].

2 Overview

Throughout this article we refer to the number of integration variables s as the stochastic dimension, which can be in the hundreds or thousands or more (and controls the truncation error), in contrast to the spatial dimension d which is just 1, 2 or 3.

2.1 Uniform Versus Lognormal

For a given parameter ${\varvec{y}}$ we consider the parametric elliptic Dirichlet problem

$$\begin{aligned} - \nabla \cdot (a({\varvec{x}},{\varvec{y}})\,\nabla u({\varvec{x}},{\varvec{y}})) \,=\, \kappa ({\varvec{x}}) \quad \text{ for } {\varvec{x}} \text{ in } \text{ D }\,, \quad u({\varvec{x}},{\varvec{y}}) \,=\, 0 \quad \text{ for }~{\varvec{x}}~\text{ on }~\partial D\,, \end{aligned}$$

(1)

for domain $D\subset {\mathbb {R}}^d$ a bounded, convex, Lipschitz polyhedron with boundary $\partial D$, where the spatial dimension $d=1,2$, or 3 is assumed given and fixed. The differential operators in (1) are understood to be with respect to the physical variable ${\varvec{x}}$ which belongs to D. The parametric variable ${\varvec{y}}= (y_j)_{j\ge 1}$ belongs to either a bounded or unbounded domain, depending on which of the two popular formulations of the parametric coefficient $a({\varvec{x}},{\varvec{y}})$ is being considered.

Uniform Case

In the uniform case, we assume that the $y_j$ are independent and uniformly distributed on $[-\tfrac{1}{2},\tfrac{1}{2}]$, and

$$\begin{aligned} a({\varvec{x}},{\varvec{y}}) \,=\, a_0({\varvec{x}}) + \sum _{j\ge 1} y_j\, \psi _j({\varvec{x}})\,, \end{aligned}$$

(2)

with $0< a_{\min }\le a({\varvec{x}},{\varvec{y}})\le a_{\max }<\infty$ for all ${\varvec{x}}$ and ${\varvec{y}}$. We need further assumptions on $a_0$ and $\psi _j$, see [31] for details. Here we mention only one important assumption that there exists $p_0\in (0,1)$ such that

$$\begin{aligned} \sum _{j\ge 1} \Vert \psi _j\Vert ^{p_0}_{L_\infty } \,<\, \infty \,. \end{aligned}$$

(3)

The value of $p_0$ reflects the rate of decay of the fluctuations in (2); later we will see that it directly affects the QMC convergence rate.

Our goal is to compute the integral, i.e., the expected value, with respect to ${\varvec{y}}$, of a bounded linear functional G applied to the solution $u(\cdot ,{\varvec{y}})$ of the PDE (1)

$$\begin{aligned} \int _{\left[ -\tfrac{1}{2},\tfrac{1}{2}\right] ^{\mathbb {N}}} G(u(\cdot ,{\varvec{y}}))\,{\mathrm {d}}{\varvec{y}}\,:=\, \lim _{s\rightarrow \infty } \int _{\left[ -\tfrac{1}{2},\tfrac{1}{2}\right] ^s} G(u(\cdot ,(y_1,\ldots ,y_s,0,0,\ldots )))\,{\mathrm {d}}y_1\cdots {\mathrm {d}}y_s\,. \end{aligned}$$

(4)

Lognormal Case

In the lognormal case, we assume that the $y_j$ are independent standard normal random numbers on ${\mathbb {R}}$, and

$$\begin{aligned} a({\varvec{x}},{\varvec{y}}) \,=\, a_0({\varvec{x}})\exp \bigg (\sum _{j\ge 1} y_j\,\sqrt{\mu _j}\,\xi _j({\varvec{x}})\bigg )\,, \end{aligned}$$

(5)

where $a_0({\varvec{x}})>0$, the $\mu _j>0$ are non-increasing, and the $\xi _j$ are orthonormal in $L_2(D)$. This can arise from the KL expansion in the case where $\log (a)$ is a stationary Gaussian random field with a specified mean and covariance function; a popular choice is the Matérn covariance.

Our goal now is the integral of $G(u(\cdot ,{\varvec{y}}))$ over ${\varvec{y}}\in {\mathbb {R}}^{\mathbb {N}}$ with a countable product Gaussian measure $\mu _G({\mathrm {d}}{\varvec{y}})$ (formally, we restrict the domain to some $Y\subset {\mathbb {R}}^{\mathbb {N}}$ with full measure $\mu _G(Y) = 1$, but we omit this in the notation)

$$\begin{aligned} \int _{{\mathbb {R}}^{\mathbb {N}}} G(u(\cdot ,{\varvec{y}}))\,\prod _{j\ge 1} \phi _\mathrm{nor}(y_j)\,{\mathrm {d}}{\varvec{y}}\,=\, \int _{[0,1]^{\mathbb {N}}} G(u(\cdot ,\varPhi ^{-1}_\mathrm{nor}({\varvec{w}})))\,{\mathrm {d}}{\varvec{w}}\,, \end{aligned}$$

(6)

where $\phi _\mathrm{nor}(y) := \exp (-y^2/2)/\sqrt{2\pi }$ is the univariate standard normal probability density function, while $\varPhi ^{-1}_\mathrm{nor}$ denotes the inverse of the corresponding cumulative distribution function, and is applied component-wise to a vector. The transformed integral over the unit cube on the right-hand side of (6) is obtained by the change of variables ${\varvec{y}}= \varPhi ^{-1}_\mathrm{nor}({\varvec{w}})$.

2.2 Single-Level Versus Multi-level

Single-Level Algorithms

We approximate the integral (4) or (6) in three steps:

• i. Dimension truncation: the infinite sum in (2) or (5) is truncated to s terms.

• ii. Finite element discretization: the PDE (1) in weak formulation (see (13) below) is solved using a finite element method with meshwidth h.

• iii. QMC quadrature: the integral of the finite element solution for the truncated problem is estimated using a deterministic or randomized QMC method.

The deterministic version of this algorithm is

$$\begin{aligned} \frac{1}{n} \sum _{i=1}^{n} G(u^s_h(\cdot ,{\varvec{y}}_i))\,, \qquad {\varvec{y}}_i \,=\, {\left\{ \begin{array}{ll} {\varvec{t}}_i - \tfrac{\varvec{1}}{\varvec{2}} &{} \text{ for } \text{ uniform }, \\ \varPhi ^{-1}_\mathrm{nor}({\varvec{t}}_i) &{} \text{ for } \text{ lognormal }, \end{array}\right. } \end{aligned}$$

(7)

where ${\varvec{t}}_1,\ldots ,{\varvec{t}}_n \in [0,1]^s$ are n QMC points from the s-dimensional standard unit cube. In the uniform case, these points are translated to the unit cube $[-\tfrac{1}{2},\frac{1}{2}]^s$. In the lognormal case, these points are mapped to the Euclidean space ${\mathbb {R}}^s$ by applying the inverse of the cumulative normal distribution function component-wise.

A randomized version of this algorithm with random shifting is given by

$$\begin{aligned} \frac{1}{r} \sum _{k=1}^{r} \frac{1}{n} \sum _{i=1}^{n} G(u^s_h(\cdot ,{\varvec{y}}_{i,k}))\,, \qquad {\varvec{y}}_{i,k} \,=\, {\left\{ \begin{array}{ll} \{{\varvec{t}}_i + {\varvec{\varDelta }}_k\} - \tfrac{\varvec{1}}{\varvec{2}} &{} \text{ for } \text{ uniform }, \\ \varPhi ^{-1}_\mathrm{nor}(\{{\varvec{t}}_i + {\varvec{\varDelta }}_k\}) &{} \text{ for } \text{ lognormal }, \end{array}\right. } \end{aligned}$$

(8)

where ${\varvec{t}}_1,\ldots ,{\varvec{t}}_n \in [0,1]^s$ are n QMC points as above, and ${\varvec{\varDelta }}_1,\ldots ,{\varvec{\varDelta }}_r \in [0,1]^s$ are r independent random shifts generated from the uniform distribution on $[0,1]^s$. The braces in $\{{\varvec{t}}_i + {\varvec{\varDelta }}_k\}$ mean that we take the fractional part of each component in the vector ${\varvec{t}}_i + {\varvec{\varDelta }}_k$. Other randomization strategies can be used analogously but need to be chosen appropriately to preserve the special properties of the QMC points. Randomized algorithms have the advantages of being unbiased as well as providing a practical error estimate.

Multi-level Algorithms

The general concept of multi-level can be explained as follows (see e.g., [17]): if we denote the integral (4) or (6) by $I_\infty$ and define a sequence $I_0, I_1, \ldots$ of approximations converging to $I_\infty$, then we can write $I_\infty$ as a telescoping sum $I_\infty = (I_\infty - I_L) + \sum _{\ell =0}^L (I_\ell - I_{\ell -1})$, $I_{-1}:=0$, and then apply different quadrature rules to the differences $I_\ell - I_{\ell -1}$, which we anticipate to get smaller as $\ell$ increases. Here we define $I_\ell$ to be the integral of $G(u^{s_\ell }_{h_\ell })$ corresponding to the finite element solution with meshwidth $h_\ell$, for the truncated problem with $s_\ell$ terms, where $1 \le s_0 \le s_1 \le s_2 \le \cdots \le s_L \le \cdots$ and $h_0 \ge h_1 \ge h_2 \ge \cdots \ge h_L \ge \cdots > 0$, so that $I_\ell$ becomes a better approximation to $I_\infty$ as $\ell$ increases.

The deterministic version of our multi-level algorithm takes the form (remembering the linearity of G)

$$\begin{aligned} \sum _{\ell =0}^L \bigg (\frac{1}{n_\ell } \sum _{i=1}^{n_\ell } G((u^{s_\ell }_{h_\ell }-u^{s_{\ell -1}}_{h_{\ell -1}}) (\cdot ,{\varvec{y}}_i^\ell ))\bigg )\,, \qquad {\varvec{y}}_i^\ell \,=\, {\left\{ \begin{array}{ll} {\varvec{t}}_i^\ell - \tfrac{\varvec{1}}{\varvec{2}} &{} \text{ for } \text{ uniform }, \\ \varPhi ^{-1}_\mathrm{nor}({\varvec{t}}_i^\ell ) &{} \text{ for } \text{ lognormal }, \end{array}\right. } \end{aligned}$$

(9)

where we apply an $s_\ell$-dimensional QMC rule with $n_\ell$ points ${\varvec{t}}_1^\ell ,\ldots ,{\varvec{t}}_{n_\ell }^\ell \in [0,1]^{s_\ell }$ to the integrand $G(u^{s_\ell }_{h_\ell }-u^{s_{\ell -1}}_{h_{\ell -1}})$, and we define $u^{s_{-1}}_{h_{-1}} :=0$.

The corresponding randomized version can be obtained analogously to (8) by taking $r_\ell$ random shifts at each level, noting that all shifts from all levels should be independent.

2.3 First-Order Versus Higher-Order

Up to this point we have said very little about QMC methods, other than noting that they are equal-weight quadrature rules as seen in (7). Actually, we will not say much about QMC methods in this article at all. In this subsection we will mention three different QMC theoretical settings which have been used for PDEs applications, giving just enough details in the first setting needed for the tutorial in Sect. 3. These three settings are discussed in slightly more detail in [30] in this volume, and more comprehensively in [31]; see also the references in these papers.

First Order QMC Over the Unit Cube – Randomly Shifted Lattice Rules for Weighted Sobolev Spaces

Suppose we wish to approximate the s-dimensional integral over the unit cube $[0,1]^s$

$$\begin{aligned} \int _{[0,1]^s} f({\varvec{y}})\, {\mathrm {d}}{\varvec{y}}\,, \end{aligned}$$

(10)

where the integrand f belongs to a weighted Sobolev space of smoothness one, with the unanchored norm defined by (see e.g., [45])

$$\begin{aligned} \Vert f\Vert _{\varvec{\gamma }}\,=\, \Bigg [ \sum _{{\mathfrak {u}}\subseteq \{1:s\}} \frac{1}{\gamma _{\mathfrak {u}}} \int _{[0,1]^{|{\mathfrak {u}}|}} \bigg (\int _{[0,1]^{s-|{\mathfrak {u}}|}} \frac{\partial ^{|{\mathfrak {u}}|}f}{\partial {\varvec{y}}_{\mathfrak {u}}}({\varvec{y}}) \,{\mathrm {d}}{\varvec{y}}_{\{1:s\}\setminus {\mathfrak {u}}} \bigg )^2 {\mathrm {d}}{\varvec{y}}_{\mathfrak {u}}\Bigg ]^{1/2}. \end{aligned}$$

(11)

Here $\{1:s\}$ is a shorthand notation for the set of indices $\{1,2,\ldots ,s\}$, $(\partial ^{|{\mathfrak {u}}|}f)/(\partial {\varvec{y}}_{\mathfrak {u}})$ denotes the mixed first derivative of f with respect to the “active” variables ${\varvec{y}}_{\mathfrak {u}}= (y_j)_{j\in {\mathfrak {u}}}$, while ${\varvec{y}}_{\{1:s\}\setminus {\mathfrak {u}}} = (y_j)_{j\in \{1:s\}\setminus {\mathfrak {u}}}$ denotes the “inactive” variables. There is a weight parameter $\gamma _{\mathfrak {u}}\ge 0$ associated with each subset of variables ${\varvec{y}}_{\mathfrak {u}}$ to moderate the relative importance between the different sets of variables. We denote the weights collectively by ${\varvec{\gamma }}$.

In this setting we pair the weighted Sobolev space with randomly shifted lattice rules; the complete theory can be found in [5]. They approximate the integral (10) by

$$ \frac{1}{n} \sum _{i=1}^n f({\varvec{t}}_i), \qquad {\varvec{t}}_i \,=\, \left\{ \frac{i\,{\varvec{z}}}{n} + {\varvec{\varDelta }}\right\} \,, $$

where ${\varvec{z}}\in {\mathbb {Z}}^s$ is known as the generating vector, ${\varvec{\varDelta }}$ is a random shift drawn from the uniform distribution over $[0,1]^s$, and as in (8) the braces indicate that we take the fractional parts of each component in a vector. It is known that good generating vectors can be obtained using a CBC construction (component-by-component construction), determining the components of ${\varvec{z}}$ one at a time sequentially, to achieve first order convergence in this setting, where the implied constant can be independent of s under appropriate conditions on the weights ${\varvec{\gamma }}$.

Specifically, if n is a power of 2 then we know that the CBC construction yields the root-mean-square error bound (with respect to the uniform random shift), for all $\lambda \in (1/2,1]$,

$$\begin{aligned} \text{ r.m.s. } \text{ error }&\,\le \, \Bigg ( \frac{2}{n} \sum _{\emptyset \ne {\mathfrak {u}}\subseteq \{1:s\}} \gamma _{\mathfrak {u}}^\lambda \, [\vartheta (\lambda )]^{|{\mathfrak {u}}|} \Bigg )^{1/(2\lambda )} \,\Vert f\Vert _{\varvec{\gamma }}\,, \end{aligned}$$

(12)

where $\vartheta (\lambda ) := 2\zeta (2\lambda )/(2\pi ^2)^\lambda$, with $\zeta (a) := \sum _{k=1}^\infty k^{-a}$ denoting the Riemann zeta function. A similar result holds for general n. The best rate of convergence clearly comes from choosing $\lambda$ close to 1 / 2.

We need some structure in the weights ${\varvec{\gamma }}$ for the CBC construction cost to be feasible in practice. Fast CBC algorithms (using FFT) can find a generating vector of a good n-point lattice rule in s dimensions in ${\mathscr {O}}(s\,n\log n)$ operations in the case of product weights, and in ${\mathscr {O}}(s\,n\log n + s^2\,n)$ operations in the case of POD weights (see (25) ahead).

First Order QMC Over ${\mathbb {R}}^s$

We can pair randomly shifted lattice rules with a special function space setting over ${\mathbb {R}}^s$ to achieve first order convergence. The norm in this function space setting includes some additional weight functions to control the behavior of the derivatives of the functions as the components go to $\pm \infty$. The root-mean-square error bound takes the same form as (12), but with a different definition of the norm and $\vartheta (\lambda )$.

Higher Order QMC Over the Unit Cube

We can pair a family of QMC methods called interlaced polynomial lattice rules with another special function space setting over the unit cube to achieve higher order convergence. The norm in this function space setting involves higher order mixed derivatives of the functions. The key advantage of this family of QMC methods over other higher order QMC methods is that, in the cost of finding a generating vector which achieves the best theoretical convergence rate, the order or the interlacing factor appears as a multiplying factor rather than sitting in the exponent of the number of points n.

3 Tutorial

We conclude from the error bound (12) that the first step in applying QMC theory is to estimate the norm of the practical integrand. We see from (7), (8), and (9) that this means we need to estimate the norms

$$ \Vert G(u^s_h)\Vert _{{\varvec{\gamma }}} \qquad \text{ and }\qquad \Vert G(u^{s_\ell }_{h_\ell }-u^{s_{\ell -1}}_{h_{\ell -1}})\Vert _{{\varvec{\gamma }}}\,, $$

for the single-level and the multi-level algorithms, respectively.

In this section we provide a step-by-step tutorial on the analysis for the single-level algorithm in the uniform case with first order QMC rules.

Differentiate the PDE

• 1. We start with the variational formulation of the PDE (1): find $u(\cdot ,{\varvec{y}})\in H^1_0(D)$ such that

  $$\begin{aligned} \int _D a({\varvec{x}},{\varvec{y}})\,\nabla u({\varvec{x}},{\varvec{y}})\cdot \nabla w({\varvec{x}})\,{\mathrm {d}}{\varvec{x}}\,=\, \int _D \kappa ({\varvec{x}})\,w({\varvec{x}})\,{\mathrm {d}}{\varvec{x}}\quad \forall w\in H^1_0(D)\,. \end{aligned}$$

  (13)

  Here we consider the Sobolev space $H^1_0(D)$ of functions which vanish on the boundary of D, with norm $\Vert w\Vert _{H^1_0} := \Vert \nabla w\Vert _{L_2}$, and together with the dual space $H^{-1}(D)$ and pivot space $L_2(D)$.

• 2. We take the mixed partial derivatives $\partial ^{{\varvec{\nu }}}$ with respect to ${\varvec{y}}$ with multi-index ${\varvec{\nu }}\ne {\varvec{0}}$ (i.e., we differentiate $\nu _j$ times with respect to $y_j$ for each j) on both sides of (13) to obtain

  $$\begin{aligned} \int _D \partial ^{{\varvec{\nu }}}\Big ( a({\varvec{x}},{\varvec{y}})\, \nabla u({\varvec{x}},{\varvec{y}})\cdot \nabla w({\varvec{x}})\Big )\,{\mathrm {d}}{\varvec{x}}\,=\, 0 \quad \forall w\in H^1_0(D)\,. \end{aligned}$$

  (14)

  We can move the derivatives inside the integrals because they operate on different variables ${\varvec{y}}$ and ${\varvec{x}}$, respectively. The right-hand side vanishes because it does not depend on ${\varvec{y}}$.

• 3. Next we apply the Leibniz product rule on the left-hand side of (14) to obtain

  $$\begin{aligned} \int _D \bigg ( \sum _{{\varvec{m}}\le {\varvec{\nu }}} \left( {\begin{array}{c}{\varvec{\nu }}\\ {\varvec{m}}\end{array}}\right) (\partial ^{{\varvec{m}}}a)({\varvec{x}},{\varvec{y}})\, \nabla (\partial ^{{\varvec{\nu }}-{\varvec{m}}} u)({\varvec{x}},{\varvec{y}})\cdot \nabla w({\varvec{x}})\bigg )\,{\mathrm {d}}{\varvec{x}}\,=\, 0 \quad \forall w\in H^1_0(D)\,, \end{aligned}$$

  (15)

  where the sum is over all multi-indices ${\varvec{m}}$ satisfying ${\varvec{m}}\le {\varvec{\nu }}$ (i.e., $m_j\le \nu _j$ for all j), and $\left( {\begin{array}{c}{\varvec{\nu }}\\ {\varvec{m}}\end{array}}\right) := \prod _{j\ge 1} \left( {\begin{array}{c}\nu _j\\ m_j\end{array}}\right)$. So far we have made no use of any assumption on $a({\varvec{x}},{\varvec{y}})$.

• 4. For the uniform case, it is easy to see from the formula (2) of $a({\varvec{x}},{\varvec{y}})$ that

  $$\begin{aligned} (\partial ^{{\varvec{m}}}a)({\varvec{x}},{\varvec{y}}) \,=\, {\left\{ \begin{array}{ll} a({\varvec{x}},{\varvec{y}}) &{}\text{ if } {\varvec{m}}={\varvec{0}}\,, \\ \psi _j({\varvec{x}}) &{}\text{ if } {\varvec{m}}={\varvec{e}}_j\,, \\ 0 &{}\text{ otherwise }\,, \end{array}\right. } \end{aligned}$$

  (16)

  where ${\varvec{e}}_j$ denotes the multi-index whose jth component is 1 and all other components are 0. Essentially, due to the linearity of a with respect to each $y_j$, if we differentiate once then we obtain $\psi _j$, and if we differentiate a second time with respect to any variable we get 0.

• 5. Substituting (16) into (15) and separating out the ${\varvec{m}}={\varvec{0}}$ term, we obtain

  $$\begin{aligned}&\int _D a({\varvec{x}},{\varvec{y}})\,\nabla (\partial ^{{\varvec{\nu }}} u)({\varvec{x}},{\varvec{y}})\cdot \nabla w({\varvec{x}})\,{\mathrm {d}}{\varvec{x}}\nonumber \\&\,=\, - \sum _{j\ge 1} \nu _j \int _D \psi _j({\varvec{x}})\, \nabla (\partial ^{{\varvec{\nu }}-{\varvec{e}}_j} u)({\varvec{x}},{\varvec{y}}) \cdot \nabla w({\varvec{x}})\,{\mathrm {d}}{\varvec{x}}\quad \forall w\in H^1_0(D)\,. \end{aligned}$$

  (17)

• 6. Note that (17) holds for all test functions in $H^1_0(D)$. We now take the particular choice of $w = (\partial ^{{\varvec{\nu }}} u)(\cdot ,{\varvec{y}})$ (yes, it is allowed to depend on ${\varvec{y}}$) in (17). Applying $a({\varvec{x}},{\varvec{y}})\ge a_{\min }$ to the left-hand side, and $|\psi _j({\varvec{x}})|\le \Vert \psi _j\Vert _{L_\infty }$ and the Cauchy–Schwarz inequality to the right-hand side, we obtain

  $$\begin{aligned}&a_{\min } \int _D |\nabla (\partial ^{{\varvec{\nu }}} u)({\varvec{x}},{\varvec{y}})|^2\,{\mathrm {d}}{\varvec{x}}\\&\,\le \, \sum _{j\ge 1} \nu _j\, \Vert \psi _j\Vert _{L_\infty } \bigg (\int _D |\nabla (\partial ^{{\varvec{\nu }}-{\varvec{e}}_j} u)({\varvec{x}},{\varvec{y}})|^2\,{\mathrm {d}}{\varvec{x}}\bigg )^{1/2} \bigg (\int _D |\nabla (\partial ^{{\varvec{\nu }}} u)({\varvec{x}},{\varvec{y}})|^2\,{\mathrm {d}}{\varvec{x}}\bigg )^{1/2}\,. \nonumber \end{aligned}$$

  (18)

• 7. Canceling one common factor from both sides of (18) and then dividing through by $a_{\min }$, we obtain the recurrence

  $$\begin{aligned} \Vert \nabla (\partial ^{{\varvec{\nu }}} u)(\cdot ,{\varvec{y}})\Vert _{L_2} \,\le \, \sum _{j\ge 1} \nu _j\, b_j\, \Vert \nabla (\partial ^{{\varvec{\nu }}-{\varvec{e}}_j} u)(\cdot ,{\varvec{y}})\Vert _{L_2}\,, \qquad b_j \,:=\, \frac{\Vert \psi _j\Vert _{L_\infty }}{a_{\min }}\,. \end{aligned}$$

  (19)

• 8. Finally we prove by induction that

  $$\begin{aligned} \Vert \nabla (\partial ^{{\varvec{\nu }}} u)(\cdot ,{\varvec{y}})\Vert _{L_2} \,\le \, |{\varvec{\nu }}|!\,{\varvec{b}}^{{\varvec{\nu }}}\, \frac{\Vert \kappa \Vert _{H^{-1}}}{a_{\min }}\,, \end{aligned}$$

  (20)

  where $|{\varvec{\nu }}| := \sum _{j\ge 1} \nu _j$ and ${\varvec{b}}^{\varvec{\nu }}:= \prod _{j\ge 1} b_j^{\nu _j}$.

  • a. Base step. We return to the variational form (13) and take $w = u(\cdot ,{\varvec{y}})$. Applying $a({\varvec{x}},{\varvec{y}})\ge a_{\min }$ to the left-hand side and estimating the right-hand side using duality pairing $|\langle \kappa , u(\cdot ,{\varvec{y}})\rangle | \le \Vert \kappa \Vert _{H^{-1}}\,\Vert u(\cdot ,{\varvec{y}})\Vert _{H^1_0}$, we obtain

    $$ a_{\min }\,\Vert \nabla u(\cdot ,{\varvec{y}})\Vert _{L_2}^2 \,\le \, \Vert \kappa \Vert _{H^{-1}}\,\Vert \nabla u(\cdot ,{\varvec{y}})\Vert _{L_2}\,, $$

    which can be rearranged to yield the case ${\varvec{\nu }}= {\varvec{0}}$ in (20).

  • b. Induction step. As the induction hypothesis, we assume that (20) holds for all multi-indices of order $< |{\varvec{\nu }}|$. Then we have

    $$ \Vert \nabla (\partial ^{{\varvec{\nu }}-{\varvec{e}}_j}u)(\cdot ,{\varvec{y}})\Vert _{L_2} \,\le \, |{\varvec{\nu }}-{\varvec{e}}_j|!\,{\varvec{b}}^{{\varvec{\nu }}-{\varvec{e}}_j}\, \frac{\Vert \kappa \Vert _{H^{-1}}}{a_{\min }}\,. $$

    Substituting this into (19) and noting that $\nu _j\,|{\varvec{\nu }}-{\varvec{e}}_j|! = |{\varvec{\nu }}|!$ and $b_j\,{\varvec{b}}^{{\varvec{\nu }}-{\varvec{e}}_j} = {\varvec{b}}^{\varvec{\nu }}$, we obtain (20) and conclude the induction.

Estimate the Norm

• 9. We want to estimate the norm $\Vert G(u^s_h)\Vert _{\varvec{\gamma }}$. We see from the definition of the norm in (11) that we need to obtain estimates on the mixed first derivatives of $G(u^s_h(\cdot ,{\varvec{y}}))$ with respect to ${\varvec{y}}$. Using linearity and boundedness of G, we have

  $$\begin{aligned} \bigg |\frac{\partial ^{|{\mathfrak {u}}|}}{\partial {\varvec{y}}_{\mathfrak {u}}} G(u^{s}_h(\cdot ,{\varvec{y}}))\bigg | \,=\, \bigg |G\bigg (\frac{\partial ^{|{\mathfrak {u}}|}}{\partial {\varvec{y}}_{\mathfrak {u}}} u^{s}_h(\cdot ,{\varvec{y}})\bigg )\bigg | \le \Vert G\Vert _{H^{-1}}\bigg \Vert \frac{\partial ^{|{\mathfrak {u}}|}}{\partial {\varvec{y}}_{\mathfrak {u}}} u^{s}_h(\cdot ,{\varvec{y}})\bigg \Vert _{H^1_0}\,. \end{aligned}$$

  (21)

• 10. We can repeat the above proof of (20) for the truncated finite element solution $u^s_h$ instead of the true solution u. Then we restrict the result to mixed first derivatives (i.e., $\nu _j\le 1$ for all j) and deduce that

  $$\begin{aligned} \bigg \Vert \frac{\partial ^{|{\mathfrak {u}}|}}{\partial {\varvec{y}}_{\mathfrak {u}}} u^{s}_h(\cdot ,{\varvec{y}})\bigg \Vert _{H^1_0} \,\le \, |{\mathfrak {u}}|! \bigg (\prod _{j\in {\mathfrak {u}}} b_j\bigg ) \frac{\Vert \kappa \Vert _{H^{-1}}}{a_{\min }}, \quad {\mathfrak {u}}\subseteq \{1:s\}\,. \end{aligned}$$

  (22)

• 11. Combining (21) with (22) and substituting the upper bound into the definition of the norm (11), we conclude that

  $$\begin{aligned} \Vert G(u^s_h)\Vert _{{\varvec{\gamma }}} \,\le \, \frac{\Vert \kappa \Vert _{H^{-1}}\Vert G\Vert _{H^{-1}}}{a_{\min }} \Bigg (\sum _{{\mathfrak {u}}\subseteq \{1:s\}} \frac{(|{\mathfrak {u}}|!)^2 \prod _{j\in {\mathfrak {u}}} b_j^2}{\gamma _{\mathfrak {u}}} \Bigg )^{1/2}\,. \end{aligned}$$

  (23)

Choose the Weights

• 12. Now we apply the upper bound on the norm (23) in the error bound for randomly shifted lattice rules (12), to yield (leaving out some constants as indicated by $\lesssim$) for all $\lambda \in (1/2,1]$,

  $$\begin{aligned} \text{ r.m.s. } \text{ error } \,\lesssim \, \Bigg ( \frac{2}{n} \sum _{{\mathfrak {u}}\subseteq \{1:s\}} \gamma _{\mathfrak {u}}^\lambda \, [\vartheta (\lambda )]^{|{\mathfrak {u}}|} \Bigg )^{1/(2\lambda )} \Bigg ( \sum _{{\mathfrak {u}}\subseteq \{1:s\}} \frac{(|{\mathfrak {u}}|!)^2 \prod _{j\in {\mathfrak {u}}} b_j^2}{\gamma _{\mathfrak {u}}} \Bigg )^{1/2}\,. \end{aligned}$$

  (24)

• 13. With elementary calculus, for any $\lambda$, we can minimize the the upper bound in (24) with respect to the weights $\gamma _{\mathfrak {u}}$ to yield the formula

  $$\begin{aligned} \gamma _{\mathfrak {u}}\,=\, \bigg (|{\mathfrak {u}}|!\prod _{j\in {\mathfrak {u}}} \frac{b_j}{\sqrt{\vartheta }(\lambda )} \bigg )^{2/(1+\lambda )}. \end{aligned}$$

  (25)

  This form of weights is called product and order dependent weights, or POD weights in short, because of the presence of some product factors as well as the cardinality of ${\mathfrak {u}}$.

• 14. We substitute (25) into (24) and simplify the expression to

  $$\begin{aligned}&\text{ r.m.s. } \text{ error } \\&\quad \lesssim \, \Bigg ( \frac{2}{n} \Bigg )^{1/(2\lambda )} \Bigg [ \sum _{{\mathfrak {u}}\subseteq \{1:s\}} \Bigg ( |{\mathfrak {u}}|! \prod _{j\in {\mathfrak {u}}} \Big (b_j\, [\vartheta (\lambda )]^{1/(2\lambda )}\Big )\Bigg )^{2\lambda /(1+\lambda )}\Bigg ]^{(1+\lambda )/(2\lambda )}\,. \nonumber \end{aligned}$$

  (26)

• 15. We now derive a condition on $\lambda$ for which the sum in (26) is bounded independently of s. In an abstract form, we have

  $$ \sum _{{\mathfrak {u}}\subseteq \{1:s\}} \bigg (|{\mathfrak {u}}|! \prod _{j\in {\mathfrak {u}}} \alpha _j\bigg )^k \,=\, \sum _{\ell =0}^s (\ell !)^k \!\! \sum _{{\mathfrak {u}}\subseteq \{1:s\},\,|{\mathfrak {u}}|=\ell } \;\; \prod _{j\in {\mathfrak {u}}} \alpha _j^k \,\le \, \sum _{\ell =0}^s (\ell !)^{k-1} \bigg (\sum _{j=1}^s \alpha _j^k\bigg )^\ell \,, $$

  where the inequality holds because each term $\prod _{j\in {\mathfrak {u}}} \alpha _j^k$ from the left-hand side of the inequality appears in the expansion $(\sum _{j=1}^s \alpha _j^k)^\ell$ exactly $\ell !$ times and yet the expansion contains other terms. The right-hand side is bounded independently of s if $\sum _{j=1}^\infty \alpha _j^k<\infty$ and $k<1$, which can be verified by the ratio test. In our case, we have $k = 2\lambda /(1+\lambda )$ and $\sum _{j=1}^\infty \alpha _j^k = [\vartheta (\lambda )]^{1/(1+\lambda )}\,\sum _{j=1}^\infty b_j^k < \infty$ if $k\ge p_0$, where we recall that $b_j$ is defined in (19) and $p_0$ is defined in (3). Hence we require

  $$\begin{aligned} p_0 \,\le \, \frac{2\lambda }{1+\lambda } \,<\, 1 \quad \Longleftrightarrow \quad \frac{p_0}{2-p_0} \,\le \, \lambda \,<\, 1\,. \end{aligned}$$

  (27)

• 16. Clearly the best rate of convergence is obtained by taking $\lambda$ as small as possible. Combining the original constraint of $\lambda \in (1/2,1]$ with (27), we now take

  $$\begin{aligned} \lambda \,=\, {\left\{ \begin{array}{ll} \displaystyle \frac{1}{2-2\delta } \text{ for } \delta \in \left( 0,\tfrac{1}{2}\right) &{} \text{ when } p_0\in \left( 0,\tfrac{2}{3}\right] , \\ \displaystyle \frac{p_0}{2-p_0} &{} \text{ when } p_0\in \left( \tfrac{2}{3},1\right) . \end{array}\right. } \end{aligned}$$

  (28)

Fast CBC Construction

• 17. The chosen weights (25) with $\lambda$ given by (28) are then fed into the CBC construction to produce tailored randomly shifted lattice rules that achieve a root-mean-square error of order

  $$ n^{-\min (1/p_0-1/2,1-\delta )}, \quad \delta \in \left( 0,\tfrac{1}{2}\right) \,, $$

  with the implied constant independent of s, where $p_0$ is given by (3). The fast CBC construction with POD weights can then find a good generating vector in ${\mathscr {O}}(s\,n\log n + s^2\,n)$ operations.

4 Key Analysis

Having completed our embedded tutorial in the previous section, we now continue to provide our overview of the analysis required in applying QMC to PDEs with random coefficients.

Some Hints at the Technical Difficulties for the Multi-level Analysis

We have seen in the uniform case with the single-level algorithm that the key is to estimate $\Vert G(u^s_h)\Vert _{\varvec{\gamma }}$, and this is achieved by estimating (see (20) and [31, Lemma 6.1])

$$ \Vert \nabla \partial ^{{\varvec{\nu }}} u(\cdot ,{\varvec{y}})\Vert _{L_2}. $$

For the multi-level algorithm, the key estimate is $\Vert G(u^{ s_\ell }_{h_\ell }-u^{s_{\ell -1}}_{h_{\ell -1}})\Vert _{{\varvec{\gamma }}}$, and we need to estimate in turn (see [31, Lemmas 6.2–6.4])

$$ \Vert \varDelta \partial ^{{\varvec{\nu }}} u(\cdot ,{\varvec{y}})\Vert _{L_2}, \quad \Vert \nabla \partial ^{{\varvec{\nu }}} (u-u_h)(\cdot ,{\varvec{y}})\Vert _{L_2}, \quad \text{ and }\quad | \partial ^{{\varvec{\nu }}} G((u-u_h)(\cdot ,{\varvec{y}}))|. $$

All three bounds involve factors of the form $(|{\varvec{\nu }}|\!+\!a_1)!\, \overline{{\varvec{b}}}^{{\varvec{\nu }}}$ for $a_1\ge 0$ and a sequence $\overline{b}_j$ similar to the previously defined $b_j$. Assuming that both the forcing term $\kappa$ and the linear functional G are in $L_2(D)$, we obtain that the second bound is of order h and the third bound is of order $h^2$. The difficulty is that we need to establish these regularity estimates simultaneously in ${\varvec{x}}$ and ${\varvec{y}}$. We also use duality tricks to gain on the convergence rate due to the linear functional G.

Some Hints at the Technical Difficulties for the Lognormal Case

For the lognormal case the argument is quite technical due to the more complicated form of $a({\varvec{x}},{\varvec{y}})$. In the single-level algorithm we need to estimate (see [31, Lemma 6.5])

$$ \Vert \nabla \partial ^{{\varvec{\nu }}} u(\cdot ,{\varvec{y}})\Vert _{L_2} \quad \text{ by } \text{ first } \text{ estimating }\quad \Vert a^{1/2}(\cdot ,{\varvec{y}})\,\nabla \partial ^{{\varvec{\nu }}} u(\cdot ,{\varvec{y}})\Vert _{L_2}\,. $$

In the multi-level algorithm we need to estimate (see [31, Lemma 6.6])

$$ \Vert \varDelta \partial ^{{\varvec{\nu }}} u(\cdot ,{\varvec{y}})\Vert _{L_2} \quad \text{ by } \text{ first } \text{ estimating }\quad \Vert a^{-1/2}(\cdot ,{\varvec{y}}) \nabla \cdot (a(\cdot ,{\varvec{y}})\,\nabla \partial ^{{\varvec{\nu }}} u(\cdot ,{\varvec{y}}))\Vert _{L_2}\,, $$

and then estimate in turn (see [31, Lemmas 6.7–6.8])

$$ \Vert a^{1/2}(\cdot ,{\varvec{y}})\nabla \partial ^{{\varvec{\nu }}} (u\!-\!u_h)(\cdot ,{\varvec{y}})\Vert _{L_2} \quad \text{ and }\quad | \partial ^{{\varvec{\nu }}} G((u-u_h)(\cdot ,{\varvec{y}}))|\,. $$

All bounds involve factors of the form $J({\varvec{y}})\,(|{\varvec{\nu }}|\!+\!a_1)!\,{\varvec{\beta }}^{{\varvec{\nu }}}$ for $a_1\ge 0$ and some sequence $\beta _j$, where $J({\varvec{y}})$ indicates some factor depending on ${\varvec{y}}$ which is not present in the uniform case. The proofs are by induction, and the tricky part is knowing what multiplying factor of $a(\cdot ,{\varvec{y}})$ should be included in the recursion. The growth of $J({\varvec{y}})$ needs to be taken into account when estimating the norm.

Summary of Results

Now we summarize and compare the results from [6, 8, 32, 33] for the uniform case:

$$\begin{aligned}&\text{ First-order } \text{ single-level } \text{[33] } \\&\quad s^{-2(1/p_0-1)} + h^{t+t'} + n^{-\min (1/p_0-1/2,1-\delta )} \quad \text{(r.m.s.) } \\&\text{ First-order } \text{ multi-level } \text{[34] } \\&\quad s_L^{-2(1/p_0-1)} + h_L^{t+t'} + \sum _{\ell =0}^L n_\ell ^{-\min (1/p_1-1/2,1-\delta )} \big (\theta _{\ell -1}\,s_{\ell -1}^{-(1/p_0-1/p_1)} + h_{\ell -1}^{t+t'}\big ) \quad \text{(r.m.s.) } \\&\text{ Higher-order } \text{ single-level } \text{[4] } \\&\quad s^{-2(1/p_0-1)} + h^{t+t'} + n^{-1/p_0} \\&\text{ Higher-order } \text{ multi-level } \text{[6] } \\&\quad s_L^{-2(1/p_0-1)} + h_L^{t+t'} + \sum _{\ell =0}^L n_\ell ^{-1/p_t} \big (\theta _{\ell -1}\,s_{\ell -1}^{-(1/p_0-1/p_t)} + h_{\ell -1}^{t+t'} \big ) \end{aligned}$$

For the first-order results, the “r.m.s.” in brackets indicates that the error is in the root-mean-square sense since we use a randomized QMC method. The higher-order results are deterministic. Without giving the full details, we simply say that the results include general parameters t and $t'$ for the regularity of $\kappa$ and G, respectively. Recall that $p_0$ corresponds to the summability of $\Vert \psi _j\Vert _{L_\infty }$, see (3). Here $p_1$ corresponds essentially to the summability of $\Vert \nabla \psi _j\Vert _{L_\infty }$, while $p_t$ corresponds analogously to higher derivatives of $\psi _j$. For the multi-level results we include the analysis for potentially taking different $s_\ell$ at each level: $\theta _{\ell -1}$ is 0 if $s_{\ell } = s_{\ell -1}$ and is 1 otherwise.

In the single-level algorithms, the error is the sum of three terms. In the multi-level algorithms, we see the multiplicative effect between the finite element error and the QMC error. However, comparing $p_1$ and $p_t$ with $p_0$, we see that multi-level algorithms need stronger regularity in ${\varvec{x}}$ than single-level algorithms.

Going from first-order to higher-order results, we see that the cap of $n^{-(1-\delta )}$ is removed. We also see a gain of an extra factor of $n^{-1/2}$; this benefit appears to arise from the switch of function space setting to a non-Hilbert space.

The error versus cost analysis depends crucially on the cost assumptions. For the single-level algorithms, we simply choose n, s and h to balance three errors. In the multi-level algorithms, we choose $n_\ell ,s_\ell ,h_\ell$ to minimize the total cost for a fixed total error using Lagrange multiplier arguments.

For the lognormal case we have similar first order results, see [22, 34]. There is no higher order results for the lognormal case because presently there is no QMC theory in this setting.

5 Software

The software package QMC4PDE accompanies the survey [31], see https://people.cs.kuleuven.be/~dirk.nuyens/qmc4pde/. Here we very briefly outline its usage.

Construction of the Generating Vector in Python

In the analysis for the PDE problems we obtain generic bounds on mixed derivatives of the form

$$ |\partial ^{{\varvec{\nu }}} F({\varvec{y}})| \,\lesssim \, \big ( (|{\varvec{\nu }}|+a_1)! \big )^{d_1} \prod _{j=1}^s (a_2 {\mathscr {B}}\!_j)^{\nu _j} \exp (a_3 {\mathscr {B}}\!_j |y_j|), $$

for some constants $a_1$, $a_2$, $a_3$, $d_1$ and some sequence ${\mathscr {B}}\!_j$, where

$$ F({\varvec{y}}) \,=\, {\left\{ \begin{array}{ll} G(u^s_h) &{} \text{ for } \text{ single-level } \text{ algorithms }, \\ G(u^s_{h_\ell } - u^s_{h_{\ell -1}}) &{} \text{ for } \text{ multi-level } \text{ algorithms }, \end{array}\right. } $$

and in particular

$$ {\left\{ \begin{array}{ll} a_3 = 0 &{} \text{ for } \text{ the } \text{ uniform } \text{ case }, \\ a_3 > 0 &{} \text{ for } \text{ the } \text{ lognormal } \text{ case }. \end{array}\right. } $$

The Python construction script takes the number of points (as a power of 2), the dimension, and all these parameters as input from the user, works out the appropriate weights $\gamma _{\mathfrak {u}}$, and then constructs a good generating vector for the QMC rule. This is either a lattice sequence (constructed following a minimax strategy as described in [2]) or an interlaced polynomial lattice rule. In the latter case the script also assembles the interlaced generating matrices, because this is the most convenient way to generate the points.

• To construct a generating vector for a lattice sequence (output written to file z.txt)

• To construct generating matrices for an interlaced polynomial lattice rule (output written to file Bs53.col)

Point Generators in Matlab/Octave (also available in C++ and Python)

Here are some Matlab/Octave usage examples for generating the actual QMC point sets from the output files of the Python construction script.

• To generate a lattice sequence (specified by the file z.txt)

• To generate an interlaced polynomial lattice rule (specified by the file Bs53.col)

The same function digitalseq_b2g can also be used to generate interlaced Sobol$'$ points by specifying the corresponding interlaced generating matrices. The parameters for generating Sobol$'$ points are taken from [28].

• To generate an interlaced Sobol$'$ sequence (interlaced matrices specified by the file sobol_alpha3_Bs53.col)

The last example produces interlaced Sobol$'$ points with interlacing factor $\alpha =3$. They can provide third order convergence if the integrand has sufficient smoothness.

6 Concluding Remarks

QMC (deterministic or randomized) convergence rate and implied constant can be independent of the dimension. This is achieved by working in a weighted function space setting. To apply QMC theory, we need an estimate of the norm of the integrand, and in turn this can help us to choose appropriate weights for the function space. The chosen weights then enter the fast CBC construction of the generating vector for the QMC points. The pairing between the function space setting and the QMC method is very important, in the sense that we want to achieve the best possible convergence rate under the weakest assumption on the problem. In practice, it may be that an off-the-shelf QMC rule works just as well, barring no theory.

In this article we considered multi-level algorithms. There are other cost saving strategies for the lognormal case and for other general situations, see e.g., [7, 25] as well as [18, 30] in this volume. Moreover, there have been many others developments on the application of QMC to PDEs with random coefficients, for some examples see the last part of the introduction.