MATHICSE Technical Report : Multi-index stochastic collocation convergence rates for random PDEs with parametric regularity

We analyze the recent Multi-index Stochastic Collocation (MISC) method for computing statistics of the solution of a partial differential equation with random data, where the random coefficient is parametrized by means of a countable sequence of terms in a suitable expansion. MISC is a combination technique based on mixed differences of spatial approximations and quadratures over the space of random data and, naturally, the error analysis uses the joint regularity of the solution both with respect to the physical variables (the variables in the phys- ical domain) and the parametric variables (the parameters corresponding to randomness). In MISC, the number of problem solutions performed at each discretization level is not deter- mined by balancing the spatial and stochastic components of the error, but rather by suitably extending the knapsack-problem approach that we have employed in the construction of the quasi-optimal sparse-grids and Multi-index Monte Carlo methods. In this methodology, we use a greedy optimization procedure to select the most effective mixed differences to include in the MISC estimator and provide a complexity analysis based on a summability argument showing algebraic rates of convergence with respect to the overall computational work. We apply our theoretical estimates to a linear elliptic partial differential equation in which the diffusion coefficient is modeled as a random field whose realizations have spatial regularity determined by a scalar parameter (in the spirit of a Matérn covariance) and we estimate the rate of convergence in terms of the smoothness parameter, the physical dimension and the complexity of the linear solver. Numerical experiments show the effectiveness of MISC in this infinite-dimensional setting compared with Multi-index Monte Carlo, as well as the sharpness of the convergence result.

Multi-index stochastic collocation convergence rates for random PDEs with parametric regularity

Fabio Nobile, Lorenzo Tamellini

We analyze the recent Multi-index Stochastic Collocation (MISC) method for computing statistics of the solution of a partial differential equation (PDE) with random data, where the random coefficient is parametrized by means of a countable sequence of terms in a suitable expansion. MISC is a combination technique based on mixed differences of spatial approximations and quadratures over the space of random data, and naturally, the error analysis uses the joint regularity of the solution with respect to both the variables in the physical domain and parametric variables. In MISC, the number of problem solutions performed at each discretization level is not determined by balancing the spatial and stochastic components of the error, but rather by suitably extending the knapsack-problem approach employed in the construction of the quasi optimal sparse-grids and Multi-index Monte Carlo methods, i.e., we use a greedy optimization procedure to select the most effective mixed differences to include in the MISC estimator. We apply our theoretical estimates to a linear elliptic PDE in which the log-diffusion coefficient is modeled as a random field, with a covariance similar to a Matérn model, whose realizations have spatial regularity determined by a scalar parameter. We conduct a complexity analysis based on a summability argument showing algebraic rates of convergence with respect to the overall computational work. The rate of convergence depends on the smoothness parameter, the physical dimensionality and the efficiency of the linear solver. Numerical experiments show the effectiveness of MISC in this infinite dimensional setting compared with the Multi-index Monte Carlo method and compare the convergence rate against the rates predicted in our theoretical analysis.

2016

Numerical Approximation of Flows in Random Porous Media

Francesco Tesei

The objective of this thesis is to develop efficient numerical schemes to successfully tackle problems arising from the study of groundwater flows in a porous saturated medium; we deal therefore with partial differential equations(PDE) having random coefficients and we are interested in computing statistics related to specific quantities of interest (QoI), e.g. a linear functional of the solution of the PDE or the solution itself. We mainly consider the approximation of the pressure in the medium through a stochastic Darcy problem with random lognormally distributed permeability relying on Matérn-type covariance functions to take into account a wide range of possible smoothness of the permeability field. Once the problem has been reformulated in terms of a countable number of random variables, we analyze sparse grid polynomial approximations of the QoI. We propose different strategies to exploit the anisotropicity of the QoI with respect to the different random entries; to this end we consider a priori'' and a posteriori'' strategies to drive the exploration of the multi-index set that defines the sparse grid, associating a profit to each multi-index either by using explicit theoretical estimates or by actually solving the PDE and computing on the fly the corresponding sparse grid interpolant. We show on several numerical examples the effectiveness of this strategy in treating the case of smooth permeability fields. In order to cover also the case of rough input permeabilities we consider, instead, Multi Level Monte Carlo techniques based on the use of a suitable control variate. Such a control variate is obtained from the solution of an auxiliary Darcy problem with a regularized input permeability which leads to pressure distributions that are smoother and less oscillatory than the original ones, but still highly correlated with them. We use then a sparse grid approximation to compute effectively the mean of the control variate and provide explicit bounds for the corresponding estimator as well as a complexity result. We also consider groundwater transport problems and focus, in particular, on arrival times properly defined starting from particle trajectories driven by the stochastic Darcy velocity and subject to molecular diffusion taking place at porous level. In this case, by using suitable PDEs whose solution can be linked to specific expectations (with respect to all Brownian motions) thanks to the famous Feynman-Kac formula, we compute statistics of such arrival times, e.g. their expected value or the probability of exiting the physical domain in a given time horizon. We discuss several scenarios and readapt the methodologies previously developed involving adaptive sparse grid stochastic collocation and Monte Carlo type schemes to this case.

EPFL2016

An anisotropic sparse grid stochastic collocation method for partial differential equations with random input data

Fabio Nobile

This work proposes and analyzes an anisotropic sparse grid stochastic collocation method for solving partial differential equations with random coefficients and forcing terms ( input data of the model). The method consists of a Galerkin approximation in the space variables and a collocation, in probability space, on sparse tensor product grids utilizing either Clenshaw-Curtis or Gaussian knots. Even in the presence of nonlinearities, the collocation approach leads to the solution of uncoupled deterministic problems, just as in the Monte Carlo method. This work includes a priori and a posteriori procedures to adapt the anisotropy of the sparse grids to each given problem. These procedures seem to be very effective for the problems under study. The proposed method combines the advantages of isotropic sparse collocation with those of anisotropic full tensor product collocation: the first approach is effective for problems depending on random variables which weigh approximately equally in the solution, while the benefits of the latter approach become apparent when solving highly anisotropic problems depending on a relatively small number of random variables, as in the case where input random variables are Karhunen-Loeve truncations of "smooth" random fields. This work also provides a rigorous convergence analysis of the fully discrete problem and demonstrates ( sub) exponential convergence in the asymptotic regime and algebraic convergence in the preasymptotic regime, with respect to the total number of collocation points. It also shows that the anisotropic approximation breaks the curse of dimensionality for a wide set of problems. Numerical examples illustrate the theoretical results and are used to compare this approach with several others, including the standard Monte Carlo. In particular, for moderately large-dimensional problems, the sparse grid approach with a properly chosen anisotropy seems to be very efficient and superior to all examined methods.