Search

We propose a sparse algebra for samplet compressed kernel matrices to enable efficient scattered data analysis. We show that the compression of kernel matrices by means of samplets produces optimally sparse matrices in a certain S-format. The compression can be performed in cost and memory that scale essentially linearly with the number of data points for kernels of finite differentiability. The same holds true for the addition and multiplication of S-formatted matrices. We prove that the inverse of a kernel matrix, given that it exists, is compressible in the S-format as well. The use of selected inversion allows to directly compute the entries in the corresponding sparsity pattern. Moreover, S-formatted matrix operations enable the efficient, approximate computation of more complicated matrix functions such as A α or exp (A) of a matrix A . The matrix algebra is justified mathematically by pseudo differential calculus. As an application, we consider Gaussian process learning algorithms for implicit surfaces. Numerical results are presented to illustrate and quantify our findings. [ABSTRACT FROM AUTHOR]

We analyze rates of approximation by quantized, tensor-structured representations of functions with isolated point singularities in ℝ3. We consider functions in countably normed Sobolev spaces with radial weights and analytic- or Gevrey-type control of weighted semi-norms. Several classes of boundary value and eigenvalue problems from science and engineering are discussed whose solutions belong to the countably normed spaces. It is shown that quantized, tensor-structured approximations of functions in these classes exhibit tensor ranks bounded polylogarithmically with respect to the accuracy ε ∈ (0,1) in the Sobolev space H1. We prove exponential convergence rates of three specific types of quantized tensor decompositions: quantized tensor train (QTT), transposed QTT and Tucker QTT. In addition, the bounds for the patchwise decompositions are uniform with respect to the position of the point singularity. An auxiliary result of independent interest is the proof of exponential convergence of hp-finite element approximations for Gevrey-regular functions with point singularities in the unit cube Q = (0,1)3. Numerical examples of function approximations and of Schrödinger-type eigenvalue problems illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

For a parameter dimension d ∈ N , we consider the approximation of many-parametric maps u : [ - 1 , 1 ] d → R by deep ReLU neural networks. The input dimension d may possibly be large, and we assume quantitative control of the domain of holomorphy of u: i.e., u admits a holomorphic extension to a Bernstein polyellipse E ρ 1 × ⋯ × E ρ d ⊂ C d of semiaxis sums ρ i > 1 containing [ - 1 , 1 ] d . We establish the exponential rate O (exp (- b N 1 / (d + 1))) of expressive power in terms of the total NN size N and of the input dimension d of the ReLU NN in W 1 , ∞ ([ - 1 , 1 ] d) . The constant b > 0 depends on (ρ j) j = 1 d which characterizes the coordinate-wise sizes of the Bernstein-ellipses for u. We also prove exponential convergence in stronger norms for the approximation by DNNs with more regular, so-called "rectified power unit" activations. Finally, we extend DNN expression rate bounds also to two classes of non-holomorphic functions, in particular to d-variate, Gevrey-regular functions, and, by composition, to certain multivariate probability distribution functions with Lipschitz marginals. [ABSTRACT FROM AUTHOR]

For functions u ∈ H 1 (Ω) in a bounded polytope Ω ⊂ R d d = 1 , 2 , 3 with plane sides for d = 2 , 3 which are Gevrey regular in Ω ¯ \ S with point singularities concentrated at a set S ⊂ Ω ¯ consisting of a finite number of points in Ω ¯ , we prove exponential rates of convergence of hp-version continuous Galerkin finite element methods on affine families of regular, simplicial meshes in Ω . The simplicial meshes are geometrically refined towards S but are otherwise unstructured. [ABSTRACT FROM AUTHOR]

We address shape uncertainty quantification for the two-dimensional Helmholtz transmission problem, where the shape of the scatterer is the only source of uncertainty. In the framework of the so-called deterministic approach, we provide a high-dimensional parametrization for the interface. Each domain configuration is mapped to a nominal configuration, obtaining a problem on a fixed domain with stochastic coefficients. To compute surrogate models and statistics of quantities of interest, we apply an adaptive, anisotropic Smolyak algorithm, which allows to attain high convergence rates that are independent of the number of dimensions activated in the parameter space. We also develop a regularity theory with respect to the spatial variable, with norm bounds that are independent of the parametric dimension. The techniques and theory presented in this paper can be easily generalized to any elliptic problem on a stochastic domain. [ABSTRACT FROM AUTHOR]

In an open, bounded domain $$\mathrm{D}\subset {\mathbb R}^n$$ with smooth boundary $$\partial \mathrm{D}$$ or on a smooth, closed and compact, Riemannian n-manifold $$\mathcal {M}\subset {\mathbb R}^{n+1}$$ , we consider the linear operator equation $$A u = f$$ where A is a boundedly invertible, strongly elliptic pseudodifferential operator of order $$r\in {\mathbb R}$$ with analytic coefficients, covering all linear, second order elliptic PDEs as well as their boundary reductions. Here, $$f\in L^2(\Omega ;H^t)$$ is an $$H^t$$ -valued random field with finite second moments, with $$H^t$$ denoting the (isotropic) Sobolev space of (not necessarily integer) order t modelled on the domain $$\mathrm{D}$$ or manifold $$\mathcal {M}$$ , respectively. We prove that the random solution's covariance kernel $$K_u = (A^{-1}\otimes A^{-1})K_f$$ on $$\mathrm{D}\times \mathrm{D}$$ (resp. $$\mathcal {M} \times \mathcal {M}$$ ) is an asymptotically smooth function provided that the covariance function $$K_f$$ of the random data is a Schwartz distributional kernel of an elliptic pseudodifferential operator. As a consequence, numerical $$\mathcal {H}$$ -matrix calculus allows the deterministic approximation of singular covariances $$K_u$$ of the random solution $$u=A^{-1}f \in L^2(\Omega ;H^{t-r})$$ in $$\mathrm{D}\times \mathrm{D}$$ $$(\text {resp. } \mathcal {M} \times \mathcal {M})$$ with work versus accuracy essentially equal to that for the mean field approximation with splines of fixed order $$\mathrm{D}$$ $$(\text {resp. } \mathcal {M} )$$ , overcoming the curse of dimensionality in this case. [ABSTRACT FROM AUTHOR]

In this paper we analyze the numerical approximation of diffusion problems over polyhedral domains in $$\mathbb {R}^d$$ ( $$d = 1, 2,3$$ ), with diffusion coefficient $$a({\varvec{x}},\omega )$$ given as a lognormal random field, i.e., $$a({\varvec{x}},\omega ) = \exp (Z({\varvec{x}},\omega ))$$ where $${\varvec{x}}$$ is the spatial variable and $$Z({\varvec{x}}, \cdot )$$ is a Gaussian random field. The analysis presents particular challenges since the corresponding bilinear form is not uniformly bounded away from $$0$$ or $$\infty $$ over all possible realizations of $$a$$ . Focusing on the problem of computing the expected value of linear functionals of the solution of the diffusion problem, we give a rigorous error analysis for methods constructed from (1) standard continuous and piecewise linear finite element approximation in physical space; (2) truncated Karhunen-Loève expansion for computing realizations of $$a$$ (leading to a possibly high-dimensional parametrized deterministic diffusion problem); and (3) lattice-based quasi-Monte Carlo (QMC) quadrature rules for computing integrals over parameter space which define the expected values. The paper contains novel error analysis which accounts for the effect of all three types of approximation. The QMC analysis is based on a recent result on randomly shifted lattice rules for high-dimensional integrals over the unbounded domain of Euclidean space, which shows that (under suitable conditions) the quadrature error decays with $$\mathcal {O}(n^{-1+\delta })$$ with respect to the number of quadrature points $$n$$ , where $$\delta >0$$ is arbitrarily small and where the implied constant in the asymptotic error bound is independent of the dimension of the domain of integration. [ABSTRACT FROM AUTHOR]

The goal of this paper is to establish exponential convergence of hp-version interior penalty (IP) discontinuous Galerkin (dG) finite element methods for the numerical approximation of linear second-order elliptic boundary-value problems with homogeneous Dirichlet boundary conditions and piecewise analytic data in three-dimensional polyhedral domains. More precisely, we shall analyze the convergence of the hp-IP dG methods considered in [D. Schötzau, C. Schwab, T. P. Wihler, SIAM J. Numer. Anal., 51 (2013), pp. 1610-1633] based on axiparallel s-geometric anisotropic meshes and s-linear anisotropic polynomial degree distributions. [ABSTRACT FROM AUTHOR]

We construct and analyze sparse tensorized space-time Galerkin discretizations for boundary integral equations resulting from the boundary reduction of nonstationary diffusion equations with either Dirichlet or Neumann boundary conditions. The approach is based on biorthogonal multilevel subspace decompositions and a weighted sparse tensor product construction. We compare the convergence behavior of the proposed method to the standard full tensor product discretizations. In particular, we show for the problem of nonstationary heat conduction in a bounded two- or three-dimensional spatial domain that low order sparse space-time Galerkin schemes are competitive with high order full tensor product discretizations in terms of the asymptotic convergence rate of the Galerkin error in the energy norms, under lower regularity requirements on the solution. [ABSTRACT FROM AUTHOR]

We introduce and analyze hp-version discontinuous Galerkin (dG) finite element methods for the numerical approximation of linear second-order elliptic boundary-value problems in three-dimensional polyhedral domains. To resolve possible corner-, edge- and corner-edge singularities, we consider hexahedral meshes that are geometrically and anisotropically refined toward the corresponding neighborhoods. Similarly, the local polynomial degrees are increased linearly and possibly anisotropically away from singularities. We design interior penalty hp-dG methods and prove that they are well-defined for problems with singular solutions and stable under the proposed hp-refinements. We establish (abstract) error bounds that will allow us to prove exponential rates of convergence in the second part of this work. [ABSTRACT FROM AUTHOR]

A correction to the article "Quasi-Monte Carlo Methods for High-Dimensional Integration: The Standard (Weighted Hilbert Space) Setting and Beyond" that was published in the 2013 issue is presented.

We introduce and analyze hp-version discontinuous Galerkin (dG) finite element methods for the numerical approximation of linear second-order elliptic boundary-value problems in three-dimensional polyhedral domains. To resolve possible corner-, edge- and corner-edge singularities, we consider hexahedral meshes that are geometrically and anisotropically refined toward the corresponding neighborhoods. Similarly, the local polynomial degrees are increased linearly and possibly anisotropically away from singularities. We design interior penalty hp-dG methods and prove that they are well-defined for problems with singular solutions and stable under the proposed hp-refinements. We establish (abstract) error bounds that will allow us to prove exponential rates of convergence in the second part of this work. [ABSTRACT FROM AUTHOR]

A class of second order, elliptic PDEs in divergence form with stochastic and anisotropic conductivity coefficients and n known, separated microscopic length scales εi, i = 1, ..., n in a bounded domain D ⊂ ℝd is considered. Neither stationarity nor ergodicity of these coefficients is assumed. Sufficient conditions are given for the random solution to converge ℙ-a.s, as εi → 0, to a stochastic, elliptic one-scale limit problem in a tensorized domain of dimension (n + 1)d. It is shown that this stochastic limit problem admits best N-term "polynomial chaos" type approximations which converge at a rate σ > 0 that is determined by the summability of the random inputs' Karhúnen-Loève expansion. The convergence of the polynomial chaos expansion is shown to hold ℙ-a.s. and uniformly with respect to the scale parameters εi. Regularity results for the stochastic, one-scale limiting problem are established. An error bound for the approximation of the random solution at finite, positive values of the scale parameters εi is established in the case of two scales, and in the case of n > 2, scales convergence is shown, albeit without giving a convergence rate in this case. [ABSTRACT FROM AUTHOR]

The initial data and bottom topography, used as inputs in shallow water models, are prone to uncertainty due to measurement errors. We model this uncertainty statistically in terms of random shallow water equations. We extend the multilevel Monte Carlo (MLMC) algorithm to numerically approximate the random shallow water equations efficiently. The MLMC algorithm is suitably modified to deal with uncertain (and possibly uncorrelated) data on each node of the underlying topography grid by the use of a hierarchical topography representation. Numerical experiments in one and two space dimensions are presented to demonstrate the efficiency of the MLMC algorithm. [ABSTRACT FROM AUTHOR]

We consider scalar hyperbolic conservation laws in spatial dimension d ≥ 1 with stochastic initial data. We prove existence and uniqueness of a random-entropy solution and give sufficient conditions on the initial data that ensure the existence of statistical moments of any order k of this random entropy solution. We present a class of numerical schemes of multi-level Monte Carlo Finite Volume (MLMC-FVM) type for the approximation of the ensemble average of the random entropy solutions as well as of their k-point space-time correlation functions. These schemes are shown to obey the same accuracy vs. work estimate as a single application of the finite volume solver for the corresponding deterministic problem. Numerical experiments demonstrating the efficiency of these schemes are presented. In certain cases, statistical moments of discontinuous solutions are found to be more regular than pathwise solutions. [ABSTRACT FROM AUTHOR]

This paper is a contemporary review of quasi-Monte Carlo (QMC) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1]s. It first introduces the by-now standard setting of weighted Hilbert spaces of functions with square-integrable mixed first derivatives, and then indicates alternative settings, such as non-Hilbert spaces, that can sometimes be more suitable. Original contributions include the extension of the fast component-by-component (CBC) construction of lattice rules that achieve the optimal convergence order (a rate of almost 1/N, where N is the number of points, independently of dimension) to so-called “product and order dependent” (POD) weights, as seen in some recent applications. Although the paper has a strong focus on lattice rules, the function space settings are applicable to all QMC methods. Furthermore, the error analysis and construction of lattice rules can be adapted to polynomial lattice rules from the family of digital nets. [ABSTRACT FROM AUTHOR]

This paper is a contemporary review of quasi-Monte Carlo (QMC) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1]s. It first introduces the by-now standard setting of weighted Hilbert spaces of functions with square-integrable mixed first derivatives, and then indicates alternative settings, such as non-Hilbert spaces, that can sometimes be more suitable. Original contributions include the extension of the fast component-by-component (CBC) construction of lattice rules that achieve the optimal convergence order (a rate of almost 1/N, where N is the number of points, independently of dimension) to so-called "product and order dependent" (POD) weights, as seen in some recent applications. Although the paper has a strong focus on lattice rules, the function space settings are applicable to all QMC methods. Furthermore, the error analysis and construction of lattice rules can be adapted to polynomial lattice rules from the family of digital nets. [ABSTRACT FROM AUTHOR]

We define the higher order moments associated to the stochastic solution of an elliptic BVP in D⊂ Rd with stochastic input data. We prove that the k-th moment solves a deterministic problem in Dk ⊂R[d,k], for which we discuss well-posedness and regularity. We discretize the deterministic k-th moment problem using sparse grids and, exploiting a spline wavelet basis, we propose an efficient algorithm, of logarithmic-linear complexity, for solving the resulting system. [ABSTRACT FROM AUTHOR]

Presents a study on a non-stabilized hp-discontinuous Galerkin Finite Element Method (DGFEM) used for convection-diffusion problems in one space dimension. Overview of the convection-diffusion problems; Stability and convergence of the DGFEM; Details on the numerical experiments.

We establish posterior sparsity in Bayesian inversion for systems governed by operator equations with distributed parameter uncertainty subject to noisy observation data δ. We generalize the results and algorithms introduced in C Schillings and C Schwab (2013 Inverse Problems29 065011) for the particular case of scalar diffusion problems with random coefficients to broad classes of forward problems, including general elliptic and parabolic operators with uncertain coefficients, and in random domains. For countably parametric, deterministic representations of uncertain parameters in the forward problem, which belong to a specified sparsity class, we quantify analytic regularity of the likewise countably parametric, deterministic Bayesian posterior density with respect to a uniform prior on the uncertain parameter sequences and prove that the parametric, deterministic density of the Bayesian posterior belongs to the same sparsity class. Generalizing C Schillings and C Schwab (2013 Inverse Problems29 065011) and C Schwab and A M Stuart (2012 Inverse Problems28 045003) the forward problems are converted to countably parametric, deterministic operator equations. Computational Bayesian inversion amounts to numerically evaluating expectations of quantities of interest (QoIs) under the Bayesian posterior, conditional on noisy observation data. Our results imply, on the one hand, sparsity of Legendre (generalized) polynomial chaos expansions of the density of the Bayesian posterior with respect to uniform prior and, on the other hand, convergence rates for data-adaptive Smolyak integration algorithms for computational Bayesian estimation, which are independent of the dimension of the parameter space. We prove, mathematically and computationally, that for uncertain inputs with sufficient sparsity convergence rates are, in particular, superior to Markov chain Monte-Carlo sampling of the posterior, in terms of the number N of instances of the parametric forward problem to be solved. [ABSTRACT FROM AUTHOR]

A correction to the article "Quasi-Monte Carlo Methods or High-Dimensional Integration: The Standard (Weighted Hilbert Space) Setting and Beyond," by F. Y. Kuo, Ch. Schwab, and I. H. Sloan that was published in the 2011 issue is presented.