Schedule

Abstracts

Dmitriy Bilyk: Discrepancy estimates, small ball inequalities, and hyperbolic cross approximations

In his pioneering work on irregularities of distribution, K. Roth came up with the idea that the essential information about the behavior of discrepancy function can be extracted by projecting this function onto the span of Haar functions supported by dyadic rectangles with xed volume (i.e. with xed product of frequencies). This observation, which closely resembles the concept of hyperbolic cross approximation in approximation theory, has been used in almost every important advance on discrepancy function estimates. Similar ideas have been used in other subjects and problems, such as the entropy estimates for mixed derivative function spaces or small deviations estimates for the multiparameter Gaussian processes. These problems and conjectures seem to revolve around the so-called "small ball inequality"  -an analytic estimate involving linear combinations of wavelets with frequencies living in a hyperbolic  cross. While the sharp two-dimensional versions of these problems have been resolved (in particular by methods coming from the theory of one-dimensional lacunary Fourier series), higher-dimensional analogues are still elusive and remain poorly understood, sometimes even on the level of conjectures. In this talk we shall survey the main ideas, connections, and methods in this circle of questions, and will explain some classical as well as recent results in this area. 

Top

Josef Dick: Higher order Quasi Monte-Carlo methods for PDEs with random coefficients

PDEs with random coefficients yield challenging infinite dimensional integration problems. The integrands considered are often very smooth, however, the convergence rate is limit by the behaviour of the integrand with respect to the dimension. In a recent paper (joint with F. Kuo, Q. T. Le Gia, D. Nuyens and Ch. Schwab) [1] we showed dimension independent convergence rates for higher order QMC quadrature for integrand functions in weighted spaces. The natural weights in this context are a generalization of POD weights previously studied by Kuo, Schwab and Sloan [2]. This method can be applied to parametric operator equations with uncertain parameters, which will be discussed in a related talk by Ch. Schwab.

[1] J. Dick, Frances Y. Kuo, Quoc T. Le Gia, D. Nuyens, and Ch. Schwab, Higher order QMC Galerkin discretization for parametric operator equations, Preprint 2013 (in preparation).

[2] F. Y. Kuo, Ch. Schwab, and I. H. Sloan, Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients. SIAM J. Numer. Anal., 50, 3351–3374, 2012.

Top

Dung Dinh: Hyperbolic crosses in high-dimensional approximations

We will discuss new results on explicit-in-dimension estimates of the integer points in hyperbolic crosses and applications in high-dimensional approximations, in particular, the highdimensional problems of n-width and ε-dimension (or more general, information complexity) and its tractability for some classes of functions having mixed smoothness. This talk is based on the recent joint works with Tino Ullrich and Alexey Chernov from the Hausdor f Center for Mathematics, Bonn:

[1]. Dinh Dung and T. Ullrich, N-Widths and ε-dimensions for high dimensional approximations, Foundations Comp. Math. (2013), DOI 10.1007/s10208-013-9149-9.

[2]. Alexey Chernov and Dinh Dung, New estimates for the cardinality of high-dimensional hyperbolic crosses and approximations of functions having mixed smoothness, Manuscript.

Top

Helmut Harbrecht: On multilevel quadrature for elliptic stochastic partial differential equations

In this talk, we show that the multilevel Monte Carlo method for elliptic stochastic partial differential equations can be interpreted as a sparse grid approximation. By using this interpretation, the method can straightforwardly be generalized to any given quadrature rule for high dimensional integrals like the quasi Monte Carlo method or a Gaussian quadrature. Besides the multilevel quadrature for approximating the solution's expectation, a simple and efficient modifi cation of the approach is proposed to compute the stochastic solution's variance. Numerical results are provided to demonstrate and quantify the approach

Top

Michael Gnewuch: Optimal Randomized Algorithms for Integration on Function Spaces with underlying ANOVA decomposition

In this talk we present upper and lower error bounds for the in nite-dimensional numerical integration problem on weighted Hilbert spaces with norms induced by an underlying ANOVA decomposition. Here the weights model the relative importance of di fferent groups of variables. We have results for randomized algorithms in two dffi erent cost models and our error bounds are in both settings sharp in the case of product weights and finite-intersection weights. The constructive upper error bounds are based on randomized multilevel algorithms in the fi rst cost model and randomized changing dimension algorithms in the second cost model. As example spaces of integrands we discuss Sobolev spaces with diff erent degrees of smoothness. In this setting we use quasi-Monte Carlo multilevel and changing dimension algorithms based on (interlaced) scrambled polynomial lattice rules. These algorithm can obtain higher order convergence rates that are arbitrarily close to the optimal convergence rate. The talk is based on joint work with Jan Baldeaux (UTS, Sydney) and with Josef Dick (UNSW, Sydney). Our findings are presented in full detail in the following two references:

[1] J. Baldeaux, M. Gnewuch. Optimal randomized multilevel algorithms for in nite-dimensional integration on function spaces with ANOVA-type decomposition. arXiv:1209.0882v1 [math.NA], Preprint 2012. (http://arxiv.org/abs/1209.0882)

[2] J. Dick, M. Gnewuch. Optimal randomized changing dimension algorithms for in nite-dimensional integration on function spaces with ANOVA-type decomposition, arXiv:1306.2821v1 [math.NA], Preprint 2013. (http://arxiv.org/abs/1306.2821)

Top

Stefan Heinrich: Randomized complexity of parametric problems

We present a general scheme of solving parameter-dependent numerical problems in classes of smooth functions by randomized methods. The algorithm is a multilevel Monte Carlo procedure. We demonstrate this general approach by applying it to parametric definite and indefinite integration as well as to parameter-dependent initial value problems for ordinary differential equations. Rates of convergence are obtained together with matching lower bounds. This way we determine the order of the randomized n-th minimal errors (in some cases up to logarithms), thus establishing the complexity of these problems. We also analyze the deterministic setting and give comparisons. The problems are considered in anisotropic classes of functions, including certain classes with dominating mixed derivatives. This is joint work with Th. Daun.

Top

Aicke Hinrichs: The Complexity of Numerical Integration of Smooth Functions

We study the complexity of multivariate integration for a number of classes of smooth functions. We consider deterministic algorithms using function values. In particular, we show that the curse of dimensionality holds for the class of r times continuously differentiable d-variate functions whose values are at most one the curse holds iff the bound on all derivatives up to order r does not go to zero faster than $d^{-1/2}$. We also consider the case of infinitely many differentiable functions and prove the curse if the bounds on the successive derivatives are appropriately large. The proof technique is based on a volume estimate of a neighborhood of the convex hull of n points which decays exponentially quickly if n is small relative to d. For $r = \infty$, we also study conditions for quasi-polynomial, weak and uniform weak tractability. We prove that the Clenshaw  Curtis Smolyak algorithm leads to weak tractability of the problem of integration of d-variate analytic functions defined on the unit cube with directional derivatives of all orders bounded by 1. This seems to be the first positive tractability result for the Smolyak algorithm for a normalized and unweighted problem. The space of integrands is not a tensor product space and therefore we have to develop a different proof technique. We use the polynomial exactness of the algorithm as well as an explicit bound on the operator norm of the algorithm. This is joint work with Erich Novak, Henryk Wozniakowski and Mario Ullrich.

Top

Stefan Kunis: Low rank approximations and fast algorithms

Structural properties of specific problems are exploited by classical fast algorithms to achieve their favourable computational complexity. While more general problems would not allow for a fast algorithm in infinite precision, they often do when considered for finite accuracy. We discuss the idea of such schemes which relies on low rank approximations under certain admissibility conditions and dedicated divide and conquer strategies. Examples are given for specific discretised integral operators including so-called hierarchical matrices for asymptotically smooth kernel functions, a fast Laplace transform, and generalized fast Fourier transforms.

Top

Erich Novak, Mario Ullrich and Henryk Wozniakowski: Complexity of Oscillatory Integrals

Complexity_of_Oscillatory_Integrals.pdf

Top

Dirk Nuyens: Lattice points in cubature and collocation

Lattice_points_in_cubature_and_collocation.pdf

Top

Peter Oswald: On Preconditioners for Sparse Grid Discretizations

The talk discusses some old and new results on optimal preconditioning of discretizations of elliptic problems by generalized sparse-grid discritizations. The focus is on subspace correction methods with simple subspace solvers and the optimal scaling of the subproblems, to boost performance. This is joint work with M. Griebel and A. Hullmann (Bonn).

Top

Franz-Jürgen Delvos: Blendet Fejér-type approximation

\text{Babu\v{s}ka} introduced the concept of periodic Hilbert spaces in studying optimal approximation of linear functionals. These spaces were used to study the approximation properties of trigonometric interpolation and periodic spline interpolation. We will continue the investigation of approximation by generalized Fourier partial sums constructed by Boolean methods and consider the construction of bivariate periodic Hilbert spaces and bivariate Fejér operators. In particular, we study the approximation order of blended Fejér operators.

Top

Jürgen Prestin: Periodic shift-invariant spaces

In this talk one-dimensional shift-invariant spaces of periodic functions are generalized to multivariate shift-invariant spaces on non-tensor product patterns. Here, we discuss matrix shifts, where M is a (d \times d)-integer matrix with det M>1. Accordingly, an element of the shift-invariant space spanned by a function φ is given as the linear combination


                                                        \sum_{\ell
     \in \Gamma} c_\ell \varphi(\cdot - 2\pi M^{-1}\ell),

 

where $\Gamma$ denotes the full collection of coset representatives of \mathbb{Z}^d/\Gamma \mathbb{Z}^d. Decompositions of shift-invariant spaces are given by divisibility considerations. For these spaces we discuss the dimension and construct interpolatory and orthonormal bases. Possible patterns are classified. The results are applied to construct multivariate orthogonal kernels of Dirichlet and de la Vallée Poussin type and the respective wavelets. This is joint work with R. Bergmann (Kaiserslautern) and D. Langemann 

 

Top

Klaus Ritter: Weighted Hilbert Spaces of Functions of In nitely Many Variables: Embeddings and Integration

We study some issues that arise for integration problems for functions of infinite many variables, which have recently been studied intensively in the literature.

The setting is based on a reproducing kernel K for functions on a domain D, a family of non-negative weights \gammau, where u varies over all finite subsets of N, and a probability measure \rho on D. For the construction of the function space we consider the tensor product kernels $k_u(x,y) = \prod_{j \in u} k(x_j,y_j)$with $x,y \in D^u$, as well as the weighted superposition $K = \sum_u \gamma_u k_u$.

We show that, under mild assumptions, $K$ is a reproducing kernel on a properly chosen domain $\mathbb X \subseteq D^\mathbb {N}, and $H(K)$ is the orthogonal sum of the spaces $H(\gamma_u k_u)$. Thereafter, we relate two approaches to define an integral for functions on $H(K)$,

namely via a canonical representer or with respect to the product measure $\rho^\mathbb {N}$ on $D^\mathbb {N}$. In particular, we provide sufficient conditions for the two approaches to lead to the same notion of integral.

Finally, we study embeddings between weighted Hilbert spaces in the particular case of product weights, i.e., $\gamma_u = \prod_{j \in u} \gamma_j$ for a sequence of positive reals $\gamma_j$.

Joint work with

Michael Gnewuch (TU Kaiserslautern), Mario Hefter (TU Kaiserslautern), and Sebastian Mayer (U Bonn). Partially supported by the DFG within Priority Program 1324 and by the Center for Mathematical and Computational Modelling $(\mbox{CM})^2$.

 

Top

Reinhold Schneider: Hierarchical tensor representation and best bilinear approximation

Hierarchical Tucker tensor format (Hackbusch) and Tensor Trains (TT) (Tyrtyshnikov) have been introduced recently offering stable and robust approximation by a low order cost . In case \mathcal{V} = \bigotimes_{i=1}^d   \mathcal{V}_i which is proportional to $d$ and polynomial in the ranks. We investigate the convergence of this approach with respect to the correspondent ranks and with the total amount of data required to represent the approximate tensor.

To provide examples, we refer established regularity classes, and consider (periodic) mixed Sobolev spaces and used results from Telmyakov. It turns out, that in this setting, we obtain optimal ranks, and optimal convergence w.r.t. the ranks, however our tensor representation is not optimal, so far. This result is neither surprising nor disappointing, see e.g. results of Harbrecht\& Griebel, due to the great flexibility and high adaptivity of low rank approximations. We consider also the numerical solution of parabolic PDEs in the present tensor framework

constraint by the restriction to tensors of prescribed multi-linear ranks \mathbf{r} and discussed best approximation rates.

Due to the multi-linearity, we establish a system of low dimensional nonlinear differential equations by applying Dirac Frenkel principle, which leads to a nonlinear non-linear Galerkin framework.

Top

Christoph Schwab: Quasi Monte-Carlo Integration for Parametric and Stochastic Operator Equations

Quasi_Monte-Carlo_Integration_for_Parametric_and_Stochastic_Operator_Equations.pdf

Top

Winfried Sickel: Approximation numbers of Sobolev embeddings

First we investigate optimal linear approximations (approximation numbers) in the context of isotropic periodic Sobolev spaces H^s (\mathbb{T}^d) of fractional smoothness s>0 for various equivalent norms including the natural one. The error is always measured in L_2(\mathbb{T}^d). Particular emphasize is given to the dependence of all constants on the dimension d. We capture the exact decay rate in n and the exact decay order of the constants with respect to d, which is in fact polynomial.

Secondly, we consider the approximation numbers with respect to the pairs H^s_{mix} (\mathbb{T}^d) and L_2(\mathbb{T}^d). Here H^s_{mix} (\mathbb{T}^d) denotes the Sobolev space of dominating mixed smoothness of order s. Again we are interested in the dependence of these numbers on n and d. This is joint work with Thomas Kühn (Leipzig) and Tino Ullrich (Bonn).

Top

Maxim M. Skriganov: On mean values of the Lq-discrepancies of point distributions

It will be shown in the talk that a large number of results on uniform distributions can be given as direct corollaries of two theorems on mean values of the L_q-discrepancies. As a corollary of these two theorems it can be shown that the best possible orders of the L_q-discrepancies of point distributions can be attained on very small averaging subsets. Furthermore, with special conditions these averaging subsets may even collapse to a single point. Such specific distributions can be called as self-averaging. 

 

Top

Hans Triebel: Weighted discrepancy and numerical integration in function spaces

Weighted_discrepancy_and_numerical_integration_in_function.pdf

Top

Grzegorz W. Wasilkowski: Tractability of Approximation of ∞-Variate Functions with Bounded Mixed Partial Derivatives

We present recent results on the tractability of $\psi$-weighted $L_s$ approximation for $\gamma$-weighted Banach spaces of $\infty$-variate functions whose mixed partial derivatives of order $r$ are bounded in a $\omega$-weighted $L_p$ norm. Functions from such spaces have a natural decomposition $f=\sum_u f_u$, where the summation is with respect to finite subsets $\setu\subset N_+$ and each $f_ u$ depends only on variables listed in $u$. We present corresponding multivariate decomposition methods and show that they lead to polynomial tractability under suitable assumptions concerning $\gamma$ weights and the probability density functions $\psi$ and $\omega$. For instance, suppose that the cost of evaluating functions with $d$ variables is at most exponential in $d$ and the weights $\gamma$ decay to zero sufficiently quickly. Then the cost of approximating such functions with the weightedL_s$-error at most ε is proportional to \epsilon^{-1/(r+\min(1/s-1/p,0))} ignoring logarithmic terms. This is a nearly-optimal results, since (once again ignoring logarithmic terms) it equals the complexity of the same approximation problem in the univariate case.

Top

Henryk Wozniakowski: New Notions of Tractability for Analytic Multivariate Problems

For analytic multivariate problems it is reasonable to expect an exponential convergence. This implies that an ε-approximation can be computed with cost proportional to 1+log ε-1. For such problems, it seems reasonable to de ne tractability of a d-variate problem in terms of 1 + log ε-1 and d, instead of ε-1 and d as it is done for non-analytic problems. In my talk I will survey recent results for this type of tractability for multivariate integration and approximation. The talk will be based on joint work with Josef Dick, Peter Kritzer, Gerhard Larcher and Friedrich Pillichshammer.

Top

Harry Yserentant: Mixed derivatives and hyperbolic cross spaces in quantum mechanics

The eigenfunctions of electronic Schrödinger operators and their exponentially weighted counterparts possess, roughly speaking, mixed weak derivatives of fractional order ϑ for ϑ < \frac34 in the Sobolev space H1. The bound \frac34 is best possible and can neither be reached nor surpassed. Such results are important for the study of sparse grid-like expansions of the wave functions and show that their asymptotic convergence rate measured in terms of the number of ansatz functions involved does not deteriorate with the number of electrons.  The resulting rate of convergence (not to speak of the actually reachable speed of convergence) is, however, low. The question arises which other properties of the wavefunctions, and what kind of nonlinear approximation methods as well, could help to improve this situation.

Top