Sparse grid | EPFL Graph Search

Sparse grids are numerical techniques to represent, integrate or interpolate high dimensional functions. They were originally developed by the Russian mathematician Sergey A. Smolyak, a student of Lazar Lyusternik, and are based on a sparse tensor product construction. Computer algorithms for efficient implementations of such grids were later developed by Michael Griebel and Christoph Zenger. Curse of dimensionality The standard way of representing multidimensional functions are tensor or full grids. The number of basis functions or nodes (grid points) that have to be stored and processed depend exponentially on the number of dimensions. The curse of dimensionality is expressed in the order of the integration error that is made by a quadrature of level l, with N_{l} points. The function has regularity r, i.e. is r times differentiable. The number of dimensions is d. |E_l| = O(N_l^{-\frac{r}{d}})

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

A posteriori error estimation for partial differential equations with random input data

Diane Sylvie Guignard

This thesis is devoted to the derivation of error estimates for partial differential equations with random input data, with a focus on a posteriori error estimates which are the basis for adaptive strategies. Such procedures aim at obtaining an approximation of the solution with a given precision while minimizing the computational costs. If several sources of error come into play, it is then necessary to balance them to avoid unnecessary work. We are first interested in problems that contain small uncertainties approximated by finite elements. The use of perturbation techniques is appropriate in this setting since only few terms in the power series expansion of the exact random solution with respect to a parameter characterizing the amount of randomness in the problem are required to obtain an accurate approximation. The goal is then to perform an error analysis for the finite element approximation of the expansion up to a certain order. First, an elliptic model problem with random diffusion coefficient with affine dependence on a vector of independent random variables is studied. We give both a priori and a posteriori error estimates for the first term in the expansion for various norms of the error. The results are then extended to higher order approximations and to other sources of uncertainty, such as boundary conditions or forcing term. Next, the analysis of nonlinear problems in random domains is proposed, considering the one-dimensional viscous Burgers' equation and the more involved incompressible steady-state Navier-Stokes equations. The domain mapping method is used to transform the equations in random domains into equations in a fixed reference domain with random coefficients. We give conditions on the mapping and the input data under which we can prove the well-posedness of the problems and give a posteriori error estimates for the finite element approximation of the first term in the expansion. Finally, we consider the heat equation with random Robin boundary conditions. For this parabolic problem, the time discretization brings an additional source of error that is accounted for in the error analysis. The second part of this work consists in the analysis of a random elliptic diffusion problem that is approximated in the physical space by the finite element method and in the stochastic space by the stochastic collocation method on a sparse grid. Considering a random diffusion coefficient with affine dependence on a vector of independent random variables, we derive a residual-based a posteriori error estimate that controls the two sources of error. The stochastic error estimator is then used to drive an adaptive sparse grid algorithm which aims at alleviating the so-called curse of dimensionality inherent to tensor grids. Several numerical examples are given to illustrate the performance of the adaptive procedure.

EPFL2016

Uncertainty Quantification of geochemical and mechanical compaction in layered sedimentary basins

Fabio Nobile, Anna Scotti, Lorenzo Tamellini

In this work we propose an Uncertainty Quantification methodology for sedimentary basins evolution under mechanical and geochemical compaction processes, which we model as a coupled, time-dependent, non-linear, monodimensional (depth-only) system of PDEs with uncertain parameters. While in previous works (Formaggia et al. 2013, Porta et al. 2014) we assumed a simplified depositional history with only one material, in this work we consider multi-layered basins, in which each layer is characterized by a different material, and hence by different properties. This setting requires several improvements with respect to our earlier works, both concerning the deterministic solver and the stochastic discretization. On the deterministic side, we replace the previous fixed-point iterative solver with a more efficient Newton solver at each step of the time-discretization. On the stochastic side, the multi-layered structure gives rise to discontinuities in the dependence of the state variables on the uncertain parameters, that need an appropriate treatment for surrogate modeling techniques, such as sparse grids, to be effective. We propose an innovative methodology to this end which relies on a change of coordinate system to align the discontinuities of the target function within the random parameter space. The reference coordinate system is built upon exploiting physical features of the problem at hand. We employ the locations of material interfaces, which display a smooth dependence on the random parameters and are therefore amenable to sparse grid polynomial approximations. We showcase the capabilities of our numerical methodologies through two synthetic test cases. In particular, we show that our methodology reproduces with high accuracy multi-modal probability density functions displayed by target state variables (e.g., porosity).

Elsevier2018

A posteriori error estimation for partial differential equations with random input data

Diane Sylvie Guignard

EPFL2016

Numerical Approximation of Flows in Random Porous Media

Francesco Tesei

EPFL2016

Uncertainty Quantification of geochemical and mechanical compaction in layered sedimentary basins

Fabio Nobile, Anna Scotti, Lorenzo Tamellini

Elsevier2018