Search

We introduce the multivariate decomposition finite element method for elliptic PDEs with lognormal diffusion coefficient $a=\exp(Z)$ where $Z$ is a Gaussian random field defined by an infinite series expansion $Z(\boldsymbol{y}) = \sum_{j\ge1} y_j\,\phi_j$ with $y_j\sim\mathcal{N}(0,1)$ and a given sequence of functions $\{\phi_j\}_{j\ge1}$. We use the MDFEM to approximate the expected value of a linear functional of the solution of the PDE which is an infinite-dimensional integral over the parameter space. The proposed algorithm uses the multivariate decomposition method (MDM) to compute the infinite-dimensional integral by a decomposition into finite-dimensional integrals, which we resolve using quasi-Monte Carlo (QMC) methods, and for which we use the finite element method (FEM) to solve different instances of the PDE. We develop higher-order quasi-Monte Carlo rules for integration over the finite-dimensional Euclidean space with respect to the Gaussian distribution by use of a truncation strategy. By linear transformations of interlaced polynomial lattice rules from the unit cube to a multivariate box of the Euclidean space we achieve higher-order convergence rates for functions belonging to a class of anchored Gaussian Sobolev spaces, taking into account the truncation error. Under appropriate conditions, the MDFEM achieves higher-order convergence rates in term of error versus cost, i.e., to achieve an accuracy of $O(\epsilon)$ the computational cost is $O(\epsilon^{-1/\lambda-d'/\lambda}) = O(\epsilon^{-(p^*+d'/\tau)/(1-p^*)})$ where $\epsilon^{-1/\lambda}$ and $\epsilon^{-d'/\lambda}$ are respectively the cost of the quasi-Monte Carlo cubature and the finite element approximations, with $d' = d \, (1+\delta')$ for some $\delta' \ge 0$ and $d$ the physical dimension, and $0 < p^* \le (2+d'/\tau)^{-1}$ is a parameter representing the sparsity of $\{\phi_j\}_{j\ge1}$., Comment: 49 pages

We introduce the multivariate decomposition finite element method (MDFEM) for solving elliptic PDEs with uniform random diffusion coefficients. We show that the MDFEM can be used to reduce the computational complexity of estimating the expected value of a linear functional of the solution of the PDE. The proposed algorithm combines the multivariate decomposition method (MDM), to compute infinite dimensional integrals, with the finite element method (FEM), to solve different instances of the PDE. The strategy of the MDFEM is to decompose the infinite-dimensional problem into multiple finite-dimensional ones which lends itself to easier parallelization than to solve a single large dimensional problem. Our first result adjusts the analysis of the multivariate decomposition method to incorporate the log-factor which typically appears in error bounds for multivariate quadrature, i.e., cubature, methods; and we take care of the fact that the number of points $n$ needs to come, e.g., in powers of 2 for higher order approximations. For the further analysis we specialize the cubature methods to be two types of quasi-Monte Carlo (QMC) rules, being digitally shifted polynomial lattice rules and interlaced polynomial lattice rules. The second and main contribution then presents a bound on the error of the MDFEM and shows higher-order convergence w.r.t. the total computational cost in case of the interlaced polynomial lattice rules in combination with a higher-order finite element method., Comment: 31 pages

In this paper we analyze the approximation of multivariate integrals over the Euclidean plane for functions which are analytic. We show explicit upper bounds which attain the exponential rate of convergence. We use an infinite grid with different mesh sizes and lengths in each direction to sample the function, and then truncate it. In our analysis, the mesh sizes and the truncated domain are chosen by optimally balancing the truncation error and the discretization error. This paper derives results in comparable function space settings, extended to $\R^s$, as which were recently obtained in the unit cube by Dick, Larcher, Pillichshammer and Wo{\'z}niakowski (2011). They showed that both lattice rules and regular grids, with different mesh sizes in each direction, attain exponential rates, hence motivating us to analyze only cubature formula based on regular meshes. We further also amend the analysis of older publications, e.g., Sloan and Osborn (1987) and Sugihara (1987), using lattice rules on $\R^s$ by taking the truncation error into account and extending them to take the anisotropy of the function space into account., Comment: 23 pages, 3 figures