Helmut Harbrecht

Jürgen Dölz, Helmut Harbrecht, Stefan Kurz et al.

We present an indirect higher order boundary element method utilising NURBS mappings for exact geometry representation and an interpolation-based fast multipole method for compression and reduction of computational complexity, to counteract the problems arising due to the dense matrices produced by boundary element methods. By solving Laplace and Helmholtz problems via a single layer approach we show, through a series of numerical examples suitable for easy comparison with other numerical schemes, that one can indeed achieve extremely high rates of convergence of the pointwise potential through the utilisation of higher order B-spline-based ansatz functions.

Abdul-Lateef Haji-Ali, Helmut Harbrecht, Michael Peters et al.

This article is dedicated to the anisotropic sparse grid quadrature for functions which are analytically extendable into an anisotropic tensor product domain. Taking into account this anisotropy, we end up with a dimension independent error versus cost estimate of the proposed quadrature. In addition, we provide a novel and improved estimate for the cardinality of the underlying anisotropic index set. To validate the theoretical findings, we present several examples ranging from simple quadrature problems to diffusion problems on random domains. These examples demonstrate the remarkable convergence behaviour of the anisotropic sparse grid quadrature in applications.

Michael Griebel, Helmut Harbrecht, Michael D. Multerer

Multilevel quadrature methods for parametric operator equations such as the multilevel (quasi-) Monte Carlo method are closely related to the sparse tensor product approximation between the spatial variable and the parameter. In this article, we employ this fact and reverse the multilevel quadrature method via the sparse grid construction by applying differences of quadrature rules to finite element discretizations of increasing resolution. Besides being algorithmically more efficient if the underlying quadrature rules are nested, this way of performing the sparse tensor product approximation enables the easy use of non-nested and even adaptively refined finite element meshes. Especially, we present a rigorous error and regularity analysis of the fully discrete solution, taking into account the effect of polygonal approximations to a curved physical domain and the numerical approximation of the bilinear form. Our results facilitate the construction of efficient multilevel quadrature methods based on deterministic quadrature rules. Numerical results in three spatial dimensions are provided to illustrate the approach.

Jürgen Dölz, Helmut Harbrecht, Michael D. Peters

We consider the efficient solution of strongly elliptic partial differential equations with random load based on the finite element method. The solution's two-point correlation can efficiently be approximated by means of an $\mathcal{H}$-matrix, in particular if the correlation length is rather short or the correlation kernel is non-smooth. Since the inverses of the finite element matrices which correspond to the differential operator under consideration can likewise efficiently be approximated in the $\mathcal{H}$-matrix format, we can solve the correspondent $\mathcal{H}$-matrix equation in essentially linear time by using the $\mathcal{H}$-matrix arithmetic. Numerical experiments for three-dimensional finite element discretizations for several correlation lengths and different smoothness are provided. They validate the presented method and demonstrate that the computation times do not increase for non-smooth or shortly correlated data.

Stephan Dahlke, Helmut Harbrecht, Manuela Utzinger et al.

In this paper, we are concerned with the numerical treatment of boundary integral equations by means of the adaptive wavelet boundary element method (BEM). In particular, we consider the second kind Fredholm integral equation for the double layer potential operator on patchwise smooth manifolds contained in $\mathbb{R}^3$. The corresponding operator equations are treated by means of adaptive implementations that are in complete accordance with the underlying theory. The numerical experiments demonstrate that adaptive methods really pay off in this setting. The observed convergence rates fit together very well with the theoretical predictions that can be made on the basis of a systematic investigation of the Besov regularity of the exact solution. Keywords: Besov spaces, weighted Sobolev spaces, adaptive wavelet BEM, non-linear approximation, integral equations, double layer potential operator, regularity, manifolds.

Helmut Harbrecht, Michael Peters, Marc Schmidlin

In this article, we consider elliptic diffusion problems with an anisotropic random diffusion coefficient. We model the notable direction in terms of a random vector field and derive regularity results for the solution's dependence on the random parameter. It turns out that the decay of the vector field's Karhunen-Loeve expansion entirely determines this regularity. The obtained results allow for sophisticated quadrature methods, such as the quasi-Monte Carlo method or the anisotropic sparse grid quadrature, in order to approximate quantities of interest, like the solution's mean or the variance. Numerical examples in three spatial dimensions are provided to supplement the presented theory.

Jürgen Dölz, Helmut Harbrecht, Michael D. Multerer

The multiplication of matrices is an important arithmetic operation in computational mathematics. In the context of hierarchical matrices, this operation can be realized by the multiplication of structured block-wise low-rank matrices, resulting in an almost linear cost. However, the computational efficiency of the algorithm is based on a recursive scheme which makes the error analysis quite involved. In this article, we propose a new algorithmic framework for the multiplication of hierarchical matrices. It improves currently known implementations by reducing the multiplication of hierarchical matrices towards finding a suitable low-rank approximation of sums of matrix-products. We propose several compression schemes to address this task. As a consequence, we are able to compute the best-approximation of hierarchical matrix products. A cost analysis shows that, under reasonable assumptions on the low-rank approximation method, the cost of the framework is almost linear with respect to the size of the matrix. Numerical experiments show that the new approach produces indeed the best-approximation of the product of hierarchical matrices for a given tolerance. They also show that the new multiplication can accomplish this task in less computation time than the established multiplication algorithm without error control.

Helmut Harbrecht, Marc Schmidlin

We consider elliptic diffusion problems with a random anisotropic diffusion coefficient, where, in a notable direction given by a random vector field, the diffusion strength differs from the diffusion strength perpendicular to this notable direction. The Karhunen-Loève expansion then yields a parametrisation of the random vector field and, therefore, also of the solution of the elliptic diffusion problem. We show that, given regularity of the elliptic diffusion problem, the decay of the Karhunen-Loève expansion entirely determines the regularity of the solution's dependence on the random parameter, also when considering this higher spatial regularity. This result then implies that multilevel collocation and multilevel quadrature methods may be used to lessen the computation complexity when approximating quantities of interest, like the solution's mean or its second moment, while still yielding the expected rates of convergence. Numerical examples in three spatial dimensions are provided to validate the presented theory.

Davide Baroli, Helmut Harbrecht, Michael Multerer

We consider scattered data approximation in samplet coordinates with $\ell_1$-regularization. The application of an $\ell_1$-regularization term enforces sparsity of the coefficients with respect to the samplet basis. Samplets are wavelet-type signed measures, which are tailored to scattered data. Therefore, samplets enable the use of well-established multiresolution techniques on general scattered data sets. They provide similar properties as wavelets in terms of localization, multiresolution analysis, and data compression. By using the Riesz isometry, we embed samplets into reproducing kernel Hilbert spaces and discuss the properties of the resulting functions. We argue that the class of signals that are sparse with respect to the embedded samplet basis is considerably larger than the class of signals that are sparse with respect to the basis of kernel translates. Vice versa, every signal that is a linear combination of only a few kernel translates is sparse in samplet coordinates. We propose the rapid solution of the problem under consideration by combining soft-shrinkage with the semi-smooth Newton method. Leveraging on the sparse representation of kernel matrices in samplet coordinates, this approach converges faster than the fast iterative shrinkage thresholding algorithm and is feasible for large-scale data. Numerical benchmarks are presented and demonstrate the superiority of the multiresolution approach over the single-scale approach. As large-scale applications, the surface reconstruction from scattered data and the reconstruction of scattered temperature data using a dictionary of multiple kernels are considered.

Helmut Harbrecht, Peter Zaspel

We consider the solution of elliptic problems on the tensor product of two physical domains as e.g. present in the approximation of the solution covariance of elliptic partial differential equations with random input. Previous sparse approximation approaches used a geometrically constructed multilevel hierarchy. Instead, we construct this hierarchy for a given discretized problem by means of the algebraic multigrid method (AMG). Thereby, we are able to apply the sparse grid combination technique to problems given on complex geometries and for discretizations arising from unstructured grids, which was not feasible before. Numerical results show that our algebraic construction exhibits the same convergence behaviour as the geometric construction, while being applicable even in black-box type PDE solvers.

Helmut Harbrecht, Florian Sonderegger, Remo von Rickenbach

We are concerned with the fast simulation of random fields on closed surfaces in $\mathbb{R}^3$ which are generated by the (Whittle-) Matérn class of covariance functions. To this end, we solve the underlying fractional stochastic partial differential equation with additive white noise by using an isogeometric finite element method on the surface in combination with the Balakrishnan integral representation of the solution. The solution of the underlying linear system of equations is performed by means of a geometric multigrid method that naturally underlies the isogeometric approach. Numerical results are presented to demonstrate the approach.

Michael Griebel, Helmut Harbrecht, Michael Multerer

We consider scattered data approximation on product regions of equal and different dimensionality. On each of these regions, we assume quasi-uniform but unstructured data sites and construct optimal sparse grids for scattered data interpolation on the product region. For this, we derive new improved error estimates for the respective kernel interpolation error by invoking duality arguments. An efficient algorithm to solve the underlying linear system of equations is proposed. The algorithm is based on the sparse grid combination technique, where a sparse direct solver is used for the elementary anisotropic tensor product kernel interpolation problems. The application of the sparse direct solver is facilitated by applying a samplet matrix compression to each univariate kernel matrix, resulting in an essentially sparse representation of the latter. In this way, we obtain a method that is able to deal with large problems up to billions of interpolation points, especially in case of reproducing kernels of nonlocal nature. Numerical results are presented to qualify and quantify the approach.

Helmut Harbrecht, Christoph Schwab

We prove error bounds for operator surrogates of solution operators for partial differential and boundary integral equations on families of domains which are diffeomorphic to one common reference (or latent) domain $D_{ref}$. The pullback of the PDE to $D_{ref}$ via affine-parametric shape encoding produces a collection of holomorphic parametric PDEs on $D_{ref}$. Sufficient conditions for (uniformly with respect to the parameter) well-posedness are given, implying existence, uniqueness and stability of parametric solution families on $D_{ref}$. We illustrate the abstract hypotheses by reviewing recent holomorphy results for a suite of elliptic and parabolic PDEs. Quantified parametric holomorphy implies existence of finite-parametric, discrete approximations of the parametric solution families with convergence rates in terms of the number $N$ of parameters. We obtain constructive proofs of existence of Neural and Spectral Operator surrogates for the shape-to-solution maps with error bounds and convergence rate guarantees uniform on the collection of admissible shapes. We admit principal-component shape encoders and frame decoders. Our results support in particular the (empirically reported) ability of neural operators to realize data-to-solution maps for elliptic and parabolic PDEs and BIEs that generalize across parametric families of shapes.

Dinh DÅ©ng, Helmut Harbrecht, Van Kien Nguyen et al.

In this article, we consider the solution to elliptic diffusion problems on a class of random domains obtained by log-Gaussian random homothety of the unit disk respectively an annulus. We model the problem under consideration and verify the existence and uniqueness of the random solution by path-wise pullback to the nominal unit disk respectively annulus. We prove the analytic regularity of the solution with respect to the random input parameter. We consider the numerical approximation of the random diffusion problem by means of continuous, piecewise linear Lagrangian Galerkin Finite Elements with numerical quadrature in the nominal domain, and by sparse grid interpolation and quadrature of Gauss-Hermite Smolyak and Quasi-Monte Carlo type in the parameter domain. The theoretical findings are complemented by numerical results.

Helmut Harbrecht, Michael Multerer

In this article, we introduce the concept of samplets by transferring the construction of Tausch-White wavelets to the realm of data. This way we obtain a multilevel representation of discrete data which directly enables data compression, detection of singularities and adaptivity. Applying samplets to represent kernel matrices, as they arise in kernel based learning or Gaussian process regression, we end up with quasi-sparse matrices. By thresholding small entries, these matrices are compressible to O(N log N) relevant entries, where N is the number of data points. This feature allows for the use of fill-in reducing reorderings to obtain a sparse factorization of the compressed matrices. Besides the comprehensive introduction to samplets and their properties, we present extensive numerical studies to benchmark the approach. Our results demonstrate that samplets mark a considerable step in the direction of making large data sets accessible for analysis.

Helmut Harbrecht, Nikola Ilić, Michael D. Multerer

In this article, we consider the numerical approximation of far-field statistics for acoustic scattering problems in the case of random obstacles. In particular, we consider the computation of the expected far-field pattern and the expected scattered wave away from the scatterer as well as the computation of the corresponding variances. To that end, we introduce an artificial interface, which almost surely contains all realizations of the random scatterer. At this interface, we directly approximate the second order statistics, i.e., the expectation and the variance, of the Cauchy data by means of boundary integral equations. From these quantities, we are able to rapidly evaluate statistics of the scattered wave everywhere in the exterior domain, including the expectation and the variance of the far-field. By employing a low-rank approximation of the Cauchy data's two-point correlation function, we drastically reduce the cost of the computation of the scattered wave's variance. Numerical results are provided in order to demonstrate the feasibility of the proposed approach.