Markus Bachmayr

Markus Bachmayr, Albert Cohen, Wolfgang Dahmen

We consider adaptive approximations of the parameter-to-solution map for elliptic operator equations depending on a large or infinite number of parameters, comparing approximation strategies of different degrees of nonlinearity: sparse polynomial expansions, general low-rank approximations separating spatial and parametric variables, and hierarchical tensor decompositions separating all variables. We describe corresponding adaptive algorithms based on a common generic template and show their near-optimality with respect to natural approximability assumptions for each type of approximation. A central ingredient in the resulting bounds for the total computational complexity are new operator compression results for the case of infinitely many parameters. We conclude with a comparison of the complexity estimates based on the actual approximability properties of classes of parametric model problems, which shows that the computational costs of optimized low-rank expansions can be significantly lower or higher than those of sparse polynomial expansions, depending on the particular type of parametric problem.

Markus Bachmayr, Albert Cohen, Giovanni Migliorati

We consider elliptic partial differential equations with diffusion coefficients that depend affinely on countably many parameters. We study the summability properties of polynomial expansions of the function mapping parameter values to solutions of the PDE, considering both Taylor and Legendre series. Our results considerably improve on previously known estimates of this type, in particular taking into account structural features of the affine parametrization of the coefficient. Moreover, the results carry over to more general Jacobi polynomial expansions. We demonstrate that the new bounds are sharp in certain model cases and we illustrate them by numerical experiments.

Markus Bachmayr, Wolfgang Dahmen

This paper is concerned with the development and analysis of an iterative solver for high-dimensional second-order elliptic problems based on subspace-based low-rank tensor formats. Both the subspaces giving rise to low-rank approximations and corresponding sparse approximations of lower-dimensional tensor components are determined adaptively. A principal obstruction to a simultaneous control of rank growth and accuracy turns out to be the fact that the underlying elliptic operator is an isomorphism only between spaces that are not endowed with cross norms. Therefore, as central part of this scheme, we devise a method for preconditioning low-rank tensor representations of operators. Under standard assumptions on the data, we establish convergence to the solution of the continuous problem with a guaranteed error reduction. Moreover, for the case that the solution exhibits a certain low-rank structure and representation sparsity, we derive bounds on the computational complexity, including in particular bounds on the tensor ranks that can arise during the iteration. We emphasize that such assumptions on the solution do not enter in the formulation of the scheme, which in fact is shown to detect them automatically. Our findings are illustrated by numerical experiments that demonstrate the practical efficiency of the method in high spatial dimensions.

Markus Bachmayr, Albert Cohen

Kolmogorov $n$-widths and low-rank approximations are studied for families of elliptic diffusion PDEs parametrized by the diffusion coefficients. The decay of the $n$-widths can be controlled by that of the error achieved by best $n$-term approximations using polynomials in the parametric variable. However, we prove that in certain relevant instances where the diffusion coefficients are piecewise constant over a partition of the physical domain, the $n$-widths exhibit significantly faster decay. This, in turn, yields a theoretical justification of the fast convergence of reduced basis or POD methods when treating such parametric PDEs. Our results are confirmed by numerical experiments, which also reveal the influence of the partition geometry on the decay of the $n$-widths.

Markus Bachmayr, Albert Cohen, Giovanni Migliorati

Approximation of elliptic PDEs with random diffusion coefficients typically requires a representation of the diffusion field in terms of a sequence $y=(y_j)_{j\geq 1}$ of scalar random variables. One may then apply high-dimensional approximation methods to the solution map $y\mapsto u(y)$. Although Karhunen-Loève representations are commonly used, it was recently shown, in the relevant case of lognormal diffusion fields, that they do not generally yield optimal approximation rates. Motivated by these results, we construct wavelet-type representations of stationary Gaussian random fields defined on bounded domains. The size and localization properties of these wavelets are studied, and used to obtain polynomial approximation results for the related elliptic PDE which outperform those achievable when using Karhunen-Loève representations. Our construction is based on a periodic extension of the random field, and the expansion on the domain is then obtained by simple restriction. This makes the approach easily applicable even when the computational domain of the PDE has a complicated geometry. In particular, we apply this construction to the class of Gaussian processes defined by the family of Matérn covariances.

Markus Bachmayr, Reinhold Schneider

We construct a soft thresholding operation for rank reduction of hierarchical tensors and subsequently consider its use in iterative thresholding methods, in particular for the solution of discretized high-dimensional elliptic problems. The proposed method for the latter case automatically adjusts the thresholding parameters, based only on bounds on the spectrum of the operator, such that the arising tensor ranks of the resulting iterates remain quasi-optimal with respect to the algebraic or exponential-type decay of the hierarchical singular values of the true solution. In addition, we give a modified algorithm using inexactly evaluated residuals that retains these features. The practical efficiency of the scheme is demonstrated in numerical experiments.

Benjamin Arras, Markus Bachmayr, Albert Cohen

We consider the problem of approximating an unknown function $u\in L^2(D,ρ)$ from its evaluations at given sampling points $x^1,\dots,x^n\in D$, where $D\subset \mathbb{R}^d$ is a general domain and $ρ$ is a probability measure. The approximation is picked in a linear space $V_m$ where $m=\dim(V_m)$ and computed by a weighted least squares method. Recent results show the advantages of picking the sampling points at random according to a well-chosen probability measure $μ$ that depends both on $V_m$ and $ρ$. With such a random design, the weighted least squares approximation is proved to be stable with high probability, and having precision comparable to that of the exact $L^2(D,ρ)$-orthonormal projection onto $V_m$, in a near-linear sampling regime $n\sim{m\log m}$. The present paper is motivated by the adaptive approximation context, in which one typically generates a nested sequence of spaces $(V_m)_{m\geq1}$ with increasing dimension. Although the measure $μ=μ_m$ changes with $V_m$, it is possible to recycle the previously generated samples by interpreting $μ_m$ as a mixture between $μ_{m-1}$ and an update measure $σ_m$. Based on this observation, we discuss sequential sampling algorithms that maintain the stability and approximation properties uniformly over all spaces $V_m$. Our main result is that the total number of computed sample at step $m$ remains of the order $m\log{m}$ with high probability. Numerical experiments confirm this analysis.

Markus Bachmayr, Sebastian Krämer, Max Pfeffer

We consider an iterative eigensolver for Schrödinger equations that constructs low-rank approximations of eigenfunctions with accuracy-adapted ranks, with particular focus on fermionic Schrödinger equations in second-quantized form and on matrix product state approximations enforcing particle number conservation. We provide a complete analysis of a solver based on preconditioned inverse iteration combined with rank truncation and propose a generalization to subspace iteration for the joint approximation of several eigenspaces. The practical performance of the method is illustrated by numerical tests for several model problems.

Markus Bachmayr, Albert Cohen, Dinh Dũng et al.

It has recently been demonstrated that locality of spatial supports in the parametrization of coefficients in elliptic PDEs can lead to improved convergence rates of sparse polynomial expansions of the corresponding parameter-dependent solutions. These results by themselves do not yield practically realizable approximations, since they do not cover the approximation of the arising expansion coefficients, which are functions of the spatial variable. In this work, we study the combined spatial and parametric approximability for elliptic PDEs with affine or lognormal parametrizations of the diffusion coefficients and corresponding Taylor, Jacobi, and Hermite expansions, to obtain fully discrete approximations. Our analysis yields convergence rates of the fully discrete approximation in terms of the total number of degrees of freedom. The main vehicle consists in $\ell^p$ summability results for the coefficient sequences measured in higher-order Hilbertian Sobolev norms. We also discuss similar results for non-Hilbertian Sobolev norms which arise naturally when using adaptive spatial discretizations.

Markus Bachmayr, Albert Cohen, Ronald DeVore et al.

Elliptic partial differential equations with diffusion coefficients of lognormal form, that is $a=exp(b)$, where $b$ is a Gaussian random field, are considered. We study the $\ell^p$ summability properties of the Hermite polynomial expansion of the solution in terms of the countably many scalar parameters appearing in a given representation of $b$. These summability results have direct consequences on the approximation rates of best $n$-term truncated Hermite expansions. Our results significantly improve on the state of the art estimates available for this problem. In particular, they take into account the support properties of the basis functions involved in the representation of $b$, in addition to the size of these functions. One interesting conclusion from our analysis is that in certain relevant cases, the Karhunen-Loève representation of $b$ may not be the best choice concerning the resulting sparsity and approximability of the Hermite expansion.

Markus Bachmayr, Wolfgang Dahmen

Low-rank tensor methods for the approximate solution of second-order elliptic partial differential equations in high dimensions have recently attracted significant attention. A critical issue is to rigorously bound the error of such approximations, not with respect to a fixed finite dimensional discrete background problem, but with respect to the exact solution of the continuous problem. While the energy norm offers a natural error measure corresponding to the underlying operator considered as an isomorphism from the energy space onto its dual, this norm requires a careful treatment in its interplay with the tensor structure of the problem. In this paper we build on our previous work on energy norm-convergent subspace-based tensor schemes contriving, however, a modified formulation which now enforces convergence only in $L_2$. In order to still be able to exploit the mapping properties of elliptic operators, a crucial ingredient of our approach is the development and analysis of a suitable asymmetric preconditioning scheme. We provide estimates for the computational complexity of the resulting method in terms of the solution error and study the practical performance of the scheme in numerical experiments. In both regards, we find that controlling solution errors in this weaker norm leads to substantial simplifications and to a reduction of the actual numerical work required for a certain error tolerance.