Friedrich Pillichshammer

Erich Novak, Friedrich Pillichshammer

The classical notion of extreme $L_p$ discrepancy is a quantitative measure for the irregularity of distribution of finite point sets in the $d$-dimensinal unit cube. In this paper we find a dual integration problem whose worst-case error is exactly the extreme $L_p$ discrepancy of the underlying integration nodes. Studying this integration problem we show that the extreme $L_p$ discrepancy suffers from the curse of dimensionality for all $p \in (1,\infty)$. It is known that the problem is tractable for $p=\infty$; the case $p=1$ stays open.

Peter Kritzer, Nicolas Nagel, Friedrich Pillichshammer

We investigate the periodic $L_2$-discrepancy of infinite sequences $§_d$ in $[0,1)^d$ and its analytic counterpart, the diaphony. We prove that infinite order-2 digital sequences over $\mathbb{F}_2$ attain the optimal order $L_{2,N}^{\rm per}(§_d) \le C_d (\log N)^{d/2}/N$ for all $N \in \mathbb{N}\setminus \{1\}$, matching known lower bounds for infinitely many $N \in \mathbb{N}$. This confirms the conjectured optimality of order-2 constructions. By this result, we improve upon previously known constructions using order-5 digital sequences, and reduce the underlying dimension for the interlacing construction from $5d$ to $2d$, significantly improving practicality. We establish our bounds within a broader framework of quasi-Monte Carlo integration for periodic Besov spaces $S_{p,q}^rB(\mathbb{T}^d)$ with dominating mixed smoothness $r \in (1/p,2)$, where $p,q\in [1,\infty]$. Rules based on infinite order-2 digital sequences yield worst-case errors of order $(\log N)^{(d-1)(1-1/q)} / N^{ \min(r,1)}$ for $r \not=1$, and $(\log N)^{d(1-1/q)}/N$ for $r=1$, for all $N \in \mathbb{N}\setminus\{1\}$, while preserving extensibility in $N$.

Josef Dick, Peter Kritzer, Friedrich Pillichshammer et al.

We study multivariate $L_2$-approximation for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. The weights are defined, in particular, in terms of two sequences $\boldsymbol{a} =\{a_j\}$ and $\boldsymbol{b} =\{b_j\}$ of numbers no less than one. Let $e^{L_2-\mathrm{app},Λ}(n,s)$ be the minimal worst-case error of all algorithms that use $n$ information functionals from the class $Λ$ in the $s$-variate case. We consider two classes $Λ$: the class $Λ^{\rm all}$ consists of all linear functionals and the class $Λ^{\rm std}$ consists of only function valuations. We study (EXP) exponential convergence. This means that $$ e^{L_2-\mathrm{app},Λ}(n,s) \le C(s)\,q^{\,(n/C_1(s))^{p(s)}}\quad{for all}\quad n, s \in \mathbb{N} $$ where $q\in(0,1)$, and $C,C_1,p:\mathbb{N} \rightarrow (0,\infty)$. If we can take $p(s)=p>0$ for all $s$ then we speak of (UEXP) uniform exponential convergence. We also study EXP and UEXP with (WT) weak, (PT) polynomial and (SPT) strong polynomial tractability. These concepts are defined as follows. Let $n(\e,s)$ be the minimal $n$ for which $e^{L_2-\mathrm{app},Λ}(n,s)\le \e$. Then WT holds iff $\lim_{s+\log\,\e^{-1}\to\infty}(\log n(\e,s))/(s+\log\,\e^{-1})=0$, PT holds iff there are $c,τ_1,τ_2$ such that $n(\e,s)\le cs^{τ_1}(1+\log\,\e^{-1})^{τ_2}$ for all $s$ and $\e\in(0,1)$, and finally SPT holds iff the last estimate holds for $τ_1=0$. The infimum of $τ_2$ for which SPT holds is called the exponent $τ^*$ of SPT. We prove that the results are the same for both classes $Λ$, and obtain conditions for WT, PT, SPT with and without EXP and UEXP.

Josef Dick, Dirk Nuyens, Friedrich Pillichshammer

The aim of this paper is to show that one can achieve convergence rates of $N^{-α+ δ}$ for $α> 1/2$ (and for $δ> 0$ arbitrarily small) for nonperiodic $α$-smooth cosine series using lattice rules without random shifting. The smoothness of the functions can be measured by the decay rate of the cosine coefficients. For a specific choice of the parameters the cosine series space coincides with the unanchored Sobolev space of smoothness 1. We study the embeddings of various reproducing kernel Hilbert spaces and numerical integration in the cosine series function space and show that by applying the so-called tent transformation to a lattice rule one can achieve the (almost) optimal rate of convergence of the integration error. The same holds true for symmetrized lattice rules for the tensor product of the direct sum of the Korobov space and cosine series space, but with a stronger dependence on the dimension in this case.

Jan Baldeaux, Josef Dick, Gunther Leobacher et al.

We show how to obtain a fast component-by-component construction algorithm for higher order polynomial lattice rules. Such rules are useful for multivariate quadrature of high-dimensional smooth functions over the unit cube as they achieve the near optimal order of convergence. The main problem addressed in this paper is to find an efficient way of computing the worst-case error. A general algorithm is presented and explicit expressions for base~2 are given. To obtain an efficient component-by-component construction algorithm we exploit the structure of the underlying cyclic group. We compare our new higher order multivariate quadrature rules to existing quadrature rules based on higher order digital nets by computing their worst-case error. These numerical results show that the higher order polynomial lattice rules improve upon the known constructions of quasi-Monte Carlo rules based on higher order digital nets.

Josef Dick, Christian Irrgeher, Gunther Leobacher et al.

We study the numerical approximation of integrals over $\mathbb{R}^s$ with respect to the standard Gaussian measure for integrands which lie in certain Hermite spaces of functions. The decay rate of the associated sequence is specified by a single integer parameter which determines the smoothness classes and the inner product can be expressed via $L_2$ norms of the derivatives of the function. We map higher order digital nets from the unit cube to a suitable subcube of $\mathbb{R}^s$ via a linear transformation and show that such rules achieve, apart from powers of $\log N$, the optimal rate of convergence of the integration error.

Peter Kritzer, Friedrich Pillichshammer, Henryk Wozniakowski

We study multivariate $\boldsymbol{L}_{\infty}$-approximation for a weighted Korobov space of periodic functions for which the Fourier coefficients decay exponentially fast. The weights are defined, in particular, in terms of two sequences $\boldsymbol{a}=\{a_j\}$ and $\boldsymbol{b}=\{b_j\}$ of positive real numbers bounded away from zero. We study the minimal worst-case error $e^{\boldsymbol{L}_{\infty}\mathrm{-app},Λ}(n,s)$ of all algorithms that use $n$ information evaluations from a class $Λ$ in the $s$-variate case. We consider two classes $Λ$ in this paper: the class $Λ^{\rm all}$ of all linear functionals and the class $Λ^{\rm std}$ of only function evaluations. We study exponential convergence of the minimal worst-case error, which means that $e^{\boldsymbol{L}_{\infty}\mathrm{-app},Λ}(n,s)$ converges to zero exponentially fast with increasing $n$. Furthermore, we consider how the error depends on the dimension $s$. To this end, we define the notions of $κ$-EC-weak, EC-polynomial and EC-strong polynomial tractability, where EC stands for "exponential convergence". In particular, EC-polynomial tractability means that we need a polynomial number of information evaluations in $s$ and $1+\log\,\varepsilon^{-1}$ to compute an $\varepsilon$-approximation. We derive necessary and sufficient conditions on the sequences $\boldsymbol{a}$ and $\boldsymbol{b}$ for obtaining exponential error convergence, and also for obtaining the various notions of tractability. The results are the same for both classes $Λ$.

Josef Dick, Aicke Hinrichs, Friedrich Pillichshammer

In this survey paper we discuss some tools and methods which are of use in quasi-Monte Carlo (QMC) theory. We group them in chapters on Numerical Analysis, Harmonic Analysis, Algebra and Number Theory, and Probability Theory. We do not provide a comprehensive survey of all tools, but focus on a few of them, including reproducing and covariance kernels, Littlewood-Paley theory, Riesz products, Minkowski's fundamental theorem, exponential sums, diophantine approximation, Hoeffding's inequality and empirical processes, as well as other tools. We illustrate the use of these methods in QMC using examples.

Josef Dick, Friedrich Pillichshammer

We show that the $\mathcal{L}_2$ discrepancy of the explicitly constructed infinite sequences of points $(\boldsymbol{x}_0,\boldsymbol{x}_1, \boldsymbol{x}_2,...)$ in $[0,1)^s$ over $\mathbb{F}_2$ introduced in [J. Dick, Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order. SIAM J. Numer. Anal., {\bf 46}, 1519--1553, 2008] satisfy $$\mathcal{L}_{2,N}(\{\boldsymbol{x}_0,\boldsymbol{x}_1,..., \boldsymbol{x}_{N-1}\}) \le C_s N^{-1} (\log N)^{s/2} \quad {for all} N \ge 2,$$ and $$\mathcal{L}_{2,2^m}(\{\boldsymbol{x}_0,\boldsymbol{x}_1,..., \boldsymbol{x}_{2^m-1}\}) \le C_s 2^{-m} m^{(s-1)/2} \quad {for all} m \ge 1,$$ where $C_s > 0$ is a constant independent of $N$ and $m$. These results are best possible by lower bounds in [P.D. Proinov, On the $L^2$ discrepancy of some infinite sequences. Serdica, {\bf 11}, 3--12, 1985] and [K. F. Roth, On irregularities of distribution. Mathematika, {\bf 1}, 73--79, 1954]. Further, for every $N \ge 2$ we explicitly construct finite point sets $\{\boldsymbol{y}_0,..., \boldsymbol{y}_{N-1}\}$ in $[0,1)^s$ such that $$\mathcal{L}_{2,N}(\{\boldsymbol{y}_0,\boldsymbol{y}_1,..., \boldsymbol{y}_{N-1}\}) \le C_s N^{-1} (\log N)^{(s-1)/2}.$$ Another solution for finite point sets by a different construction was previously shown in [W. W. L. Chen and M. M. Skriganov, Explicit constructions in the classical mean squares problem in irregularity of point distribution. J. Reine Angew. Math., {\bf 545}, 67--95, 2002].

Peter Kritzer, Friedrich Pillichshammer, G. W. Wasilkowski

We provide lower bounds for the norms of embeddings between $\boldsymbolγ$-weighted Anchored and ANOVA spaces of $s$-variate functions with mixed partial derivatives of order one bounded in $L_p$ norm ($p\in[1,\infty]$). In particular we show that the norms behave polynomially in $s$ for Finite Order Weights and Finite Diameter Weights if $p>1$, and increase faster than any polynomial in $s$ for Product Order-Dependent Weights and any $p$.

Josef Dick, Aicke Hinrichs, Lev Markhasin et al.

The $L_p$-discrepancy is a quantitative measure for the irregularity of distribution modulo one of infinite sequences. In 1986 Proinov proved for all $p>1$ a lower bound for the $L_p$-discrepancy of general infinite sequences in the $d$-dimensional unit cube, but it remained an open question whether this lower bound is best possible in the order of magnitude until recently. In 2014 Dick and Pillichshammer gave a first construction of an infinite sequence whose order of $L_2$-discrepancy matches the lower bound of Proinov. Here we give a complete solution to this problem for all finite $p > 1$. We consider so-called order $2$ digital $(t,d)$-sequences over the finite field with two elements and show that such sequences achieve the optimal order of $L_p$-discrepancy simultaneously for all $p \in (1,\infty)$.

Aicke Hinrichs, Peter Kritzer, Friedrich Pillichshammer et al.

The paper considers linear problems on weighted spaces of multivariate functions of many variables. The main questions addressed are: When is it possible to approximate the solution for the original function of very many variables by the solution for the same function; however with all but the first $k$ variables set to zero, so that the corresponding error is small? What is the truncation dimension, i.e., the smallest number $k=k(\varepsilon)$ such that the corresponding error is bounded by a given error demand $\varepsilon$? Surprisingly, $k(\varepsilon)$ could be very small even for weights with a modest speed of convergence to zero.

Josef Dick, Domingo Gomez-Perez, Friedrich Pillichshammer et al.

We study high-dimensional numerical integration in the worst-case setting. The subject of tractability is concerned with the dependence of the worst-case integration error on the dimension. Roughly speaking, an integration problem is tractable if the worst-case error does not explode exponentially with the dimension. Many classical problems are known to be intractable. However, sometimes tractability can be shown. Often such proofs are based on randomly selected integration nodes. Of course, in applications true random numbers are not available and hence one mimics them with pseudorandom number generators. This motivates us to propose the use of pseudorandom vectors as underlying integration nodes in order to achieve tractability. In particular, we consider digital inverse vectors and present two examples of problems, the weighted star discrepancy and integration of Hölder continuous, absolute convergent Fourier- and cosine series, where the proposed method is successful.

Peter Kritzer, Friedrich Pillichshammer, Leszek Plaskota et al.

In this paper, we study the approximation of $d$-dimensional $ρ$-weighted integrals over unbounded domains $\mathbb{R}_+^d$ or $\mathbb{R}^d$ using a special change of variables, so that quasi-Monte Carlo (QMC) or sparse grid rules can be applied to the transformed integrands over the unit cube. We consider a class of integrands with bounded $L_p$ norm of mixed partial derivatives of first order, where $p\in[1,+\infty].$ The main results give sufficient conditions on the change of variables $ν$ which guarantee that the transformed integrand belongs to the standard Sobolev space of functions over the unit cube with mixed smoothness of order one. These conditions depend on $ρ$ and $p$. The proposed change of variables is in general different than the standard change based on the inverse of the cumulative distribution function. We stress that the standard change of variables leads to integrands over a cube; however, those integrands have singularities which make the application of QMC and sparse grids ineffective. Our conclusions are supported by numerical experiments.

Aicke Hinrichs, Friedrich Pillichshammer, Shu Tezuka

We study the weighted star discrepancy of the Halton sequence. In particular, we show that the Halton sequence achieves strong polynomial tractability for the weighted star discrepancy for product weights $(γ_j)_{j \ge 1}$ under the mildest condition on the weight sequence known so far for explicitly constructive sequences. The condition requires $\sup_{d \ge 1} \max_{\emptyset \not= \mathfrak{u} \subseteq [d]} \prod_{j \in \mathfrak{u}} (j γ_j) < \infty$. The same result holds for Niederreiter sequences and for other types of digital sequences. Our results are true also for the weighted unanchored discrepancy.

Johann S. Brauchart, Josef Dick, Friedrich Pillichshammer

We prove that the information complexity (i.e., the inverse) of the classical spherical cap $L_2$ discrepancy on the $d$-dimensional sphere $\mathbb{S}^d$ decreases with dimension $d$, indicating a ``blessing of dimensionality'' for the associated numerical integration problem. We then introduce a modified spherical cap $L_2$ discrepancy that emphasizes large caps (close to hemispheres). For this variant, the problem does not become easier with increasing $d$. We also establish a Stolarsky invariance principle which connects the modified spherical cap $L_2$ discrepancy to numerical integration in the Sobolev space $H^{(d+1)/2}(\mathbb{S}^d)$, represented by the reproducing kernel $K(\boldsymbol{x}, \boldsymbol{y}) = 1 - \tfrac{1}{\sqrt{2}} \|\boldsymbol{x} - \boldsymbol{y}\|$. Stolarsky's invariance principle then implies that the worst-case integration error in this space grows polynomially with $d$.

Peter Kritzer, Friedrich Pillichshammer, G. W. Wasilkowski

We consider approximation of functions of $s$ variables, where $s$ is very large or infinite, that belong to weighted anchored spaces. We study when such functions can be approximated by algorithms designed for functions with only very small number ${\rm dim^{trnc}}(\varepsilon)$ of variables. Here $\varepsilon$ is the error demand and we refer to ${\rm dim^{trnc}}(\varepsilon)$ as the $\varepsilon$-truncation dimension. We show that for sufficiently fast decaying product weights and modest error demand (up to about $\varepsilon \approx 10^{-5}$) the truncation dimension is surprisingly very small.

Josef Dick, Friedrich Pillichshammer

The inverse of the star-discrepancy problem asks for point sets $P_{N,s}$ of size $N$ in the $s$-dimensional unit cube $[0,1]^s$ whose star-discrepancy $D^\ast(P_{N,s})$ satisfies $$D^\ast(P_{N,s}) \le C \sqrt{s/N},$$ where $C> 0$ is a constant independent of $N$ and $s$. The first existence results in this direction were shown by Heinrich, Novak, Wasilkowski, and Woźniakowski in 2001, and a number of improvements have been shown since then. Until now only proofs that such point sets exist are known. Since such point sets would be useful in applications, the big open problem is to find explicit constructions of suitable point sets $P_{N,s}$. We review the current state of the art on this problem and point out some connections to pseudo-random number generators.

Friedrich Pillichshammer

In this paper we study tractability properties of the weighted star discrepancy with general coefficients of centered regular grids with different mesh-sizes. We give exact characterizations of the weight sequences $(γ_j)_{j \ge 1}$ such that the regular grid with different mesh-sizes achieves weak, uniform weak, quasi polynomial, polynomial or strong polynomial tractability for the $\boldsymbolγ$-weighted star discrepancy. For example, a necessary and sufficient condition such that the regular grid with different mesh-sizes achieves weak tractability for the $\boldsymbolγ$-weighted star discrepancy is $\lim_{j \rightarrow \infty}j γ_j=0$.

Christian Irrgeher, Peter Kritzer, Friedrich Pillichshammer

We study multivariate integration and approximation for functions belonging to a weighted reproducing kernel Hilbert space based on half-period cosine functions in the worst-case setting. The weights in the norm of the function space depend on two sequences of real numbers and decay exponentially. As a consequence the functions are infinitely often differentiable, and therefore it is natural to expect exponential convergence of the worst-case error. We give conditions on the weight sequences under which we have exponential convergence for the integration as well as the approximation problem. Furthermore, we investigate the dependence of the errors on the dimension by considering various notions of tractability. We prove sufficient and necessary conditions to achieve these tractability notions.

Peter Kritzer, Helene Laimer, Friedrich Pillichshammer

We consider multivariate $\mathbb{L}_2$-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error $e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)$ of all algorithms that use $N$ information evaluations from the class $Λ$ in the $d$-dimensional case. The two classes $Λ$ considered in this paper are the class $Λ^{\rm all}$ consisting of all linear functionals and the class $Λ^{\rm std}$ consisting only of function evaluations. The focus lies on the dependence of $e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)$ on the dimension $d$. The main results are conditions for weak, polynomial, and strong polynomial tractability.

Josef Dick, Friedrich Pillichshammer, Kosuke Suzuki et al.

Frolov's cubature formula on the unit hypercube has been considered important since it attains an optimal rate of convergence for various function spaces. Its integration nodes are given by shrinking a suitable full rank $\mathbb{Z}$-lattice in $\mathbb{R}^d$ and taking all points inside the unit cube. The main drawback of these nodes is that they are hard to find computationally, especially in high dimensions.In such situations, quasi-Monte Carlo (QMC) rules based on digital nets have proven to be successful. However, there is still no construction known that leads to QMC rules which are optimal in the same generality as Frolov's. In this paper we investigate a polynomial analog of Frolov's cubature formula, which we expect to be important in this respect. This analog is defined in a field of Laurent series with coefficients in a finite field. A similar approach was previously studied in [M.~B.~Levin. Adelic constructions of low discrepancy sequences. Online Journal of Analytic Combinatorics. Issue 5, 2010.]. We show that our construction is a $(t,m,d)$-net, which also implies bounds on its star-discrepancy and the error of the corresponding cubature rule. Moreover, we show that our cubature rule is a QMC rule, whereas Frolov's is not, and provide an algorithm to determine its integration nodes explicitly. To this end we need to extend the notion of $(t,m,d)$-nets to fit the situation that the points can have infinite digit expansion and develop a duality theory. Additionally, we adapt the notion of admissible lattices to our setting and prove its significance.

Friedrich Pillichshammer

The theory of digital sequences is a fundamental topic in QMC theory. Digital sequences are prototypes of sequences with low discrepancy. First examples were given by Il'ya Meerovich Sobol' and by Henri Faure with their famous constructions. The unifying theory was developed later by Harald Niederreiter. Nowadays there is a magnitude of examples of digital sequences and it is classical knowledge that the star discrepancy of the initial $N$ elements of such sequences can achieve a rate of order $(\log N)^s/N$, where $s$ denotes the dimension. On the other hand, very little has been known about the $L_p$ norm of the discrepancy function of digital sequences for finite $p$, apart from evident estimates in terms of star discrepancy. In this article we give a review of some recent results on various types of discrepancy of digital sequences. This comprises: star discrepancy and weighted star discrepancy, $L_p$-discrepancy, discrepancy with respect to bounded mean oscillation and exponential Orlicz norms, as well as Sobolev, Besov and Triebel-Lizorkin norms with dominating mixed smoothness.

Peter Kritzer, Friedrich Pillichshammer, G. W. Wasilkowski

The paper considers truncation errors for functions of the form $f(x_1,x_2,\dots)=g(\sum_{j=1}^\infty x_j\,ξ_j)$, i.e., errors of approximating $f$ by $f_k(x_1,\dots,x_k)=g(\sum_{j=1}^k x_j\,ξ_j)$, where the numbers $ξ_j$ converge to zero sufficiently fast and $x_j$'s are i.i.d. random variables. As explained in the introduction, functions $f$ of the form above appear in a number of important applications. To have positive results for possibly large classes of such functions, the paper provides sharp bounds on truncation errors in both the average and worst case settings. In the former case, the functions $g$ are from a Hilbert space $G$ endowed with a zero mean probability measure with a given covariance kernel. In the latter case, the functions $g$ are from a reproducing kernel Hilbert space, or a space of functions satisfying a Hölder condition.

Josef Dick, Friedrich Pillichshammer, Kosuke Suzuki et al.

We prove upper bounds on the order of convergence of lattice based algorithms for numerical integration in function spaces of dominating mixed smoothness on the unit cube with homogeneous boundary condition. More precisely, we study worst-case integration errors for Besov spaces of dominating mixed smoothness $\mathring{\mathbf{B}}^s_{p,θ}$, which also comprise the concept of Sobolev spaces of dominating mixed smoothness $\mathring{\mathbf{H}}^s_{p}$ as special cases. The considered algorithms are quasi-Monte Carlo rules with underlying nodes from $T_N(\mathbb{Z}^d) \cap [0,1)^d$, where $T_N$ is a real invertible generator matrix of size $d$. For such rules the worst-case error can be bounded in terms of the Zaremba index of the lattice $\mathbb{X}_N=T_N(\mathbb{Z}^d)$. We apply this result to Kronecker lattices and to rank-1 lattice point sets, which both lead to optimal error bounds up to $\log N$-factors for arbitrary smoothness $s$. The advantage of Kronecker lattices and classical lattice point sets is that the run-time of algorithms generating these point sets is very short.

Christian Irrgeher, Peter Kritzer, Friedrich Pillichshammer et al.

We consider $\mathbb{L}_2$-approximation of elements of a Hermite space of analytic functions over $\mathbb{R}^s$. The Hermite space is a weighted reproducing kernel Hilbert space of real valued functions for which the Hermite coefficients decay exponentially fast. The weights are defined in terms of two sequences $\boldsymbol{a} = \{a_j\}$ and $\boldsymbol{b} = \{b_j\}$ of positive real numbers. We study the $n$th minimal worst-case error $e(n,{\rm APP}_s;Λ^{\rm std})$ of all algorithms that use $n$ information evaluations from the class $Λ^{\rm std}$ which only allows function evaluations to be used. We study (uniform) exponential convergence of the $n$th minimal worst-case error, which means that $e(n,{\rm APP}_s; Λ^{\rm std})$ converges to zero exponentially fast with increasing $n$. Furthermore, we consider how the error depends on the dimension $s$. To this end, we study the minimal number of information evaluations needed to compute an $\varepsilon$-approximation by considering several notions of tractability which are defined with respect to $s$ and $\log \varepsilon^{-1}$. We derive necessary and sufficient conditions on the sequences $\boldsymbol{a}$ and $\boldsymbol{b}$ for obtaining exponential error convergence, and also for obtaining the various notions of tractability. It turns out that the conditions on the weight sequences are almost the same as for the information class $Λ^{\rm all}$ which uses all linear functionals. The results are also constructive as the considered algorithms are based on tensor products of Gauss-Hermite rules for multivariate integration. The obtained results are compared with the analogous results for integration in the same Hermite space. This allows us to give a new sufficient condition for EC-weak tractability for integration.

Christian Irrgeher, Peter Kritzer, Friedrich Pillichshammer et al.

We study multivariate approximation defined over tensor product Hilbert spaces. The domain space is a weighted tensor product Hilbert space with exponential weights which depend on two sequences $\boldsymbol{a}=\{a_j\}_{j\in\mathbb{N}}$ and $\boldsymbol{b}=\{b_j\}_{j\in\mathbb{N}}$ of positive numbers, and on a bounded sequence of positive integers $\boldsymbol{m}=\{m_j\}_{j\in\mathbb{N}}$. The sequence $\boldsymbol{a}$ is non-decreasing and the sequence $\boldsymbol{b}$ is bounded from below by a positive number. We find necessary and sufficient conditions on $\boldsymbol{a},\boldsymbol{b}$ and $\boldsymbol{m}$ to achieve the standard and new notions of tractability in the worst case setting.

Peter Hellekalek, Peter Kritzer, Friedrich Pillichshammer

In this paper, we study quasi-Monte Carlo (QMC) integration in weighted Sobolev spaces. In contrast to many previous results the QMC algorithms considered here are of open type, i.e., they are extensible in the number of sample points without having to discard the samples already used. As the underlying integration nodes we consider randomized Halton sequences in prime bases $\boldsymbol{p}=(p_1,...,p_s)$ for which we study the root mean square (RMS) worst-case error. The randomization method is a $\boldsymbol{p}$-adic shift which is based on $\boldsymbol{p}$-adic arithmetic. The obtained error bounds are optimal in the order of magnitude of the number of sample nodes. Furthermore we obtain conditions on the coordinate weights under which the error bounds are independent of the dimension $s$. In terms of the field of Information-Based Complexity this means that the corresponding QMC rule achieves a strong polynomial tractability error bound. Our findings on the RMS worst-case error of randomized Halton sequences can be carried over to the RMS $L_2$-discrepancy. Except for the $\boldsymbol{p}$-adic shift our results are fully constructive and no search algorithms (such as the component-by-component algorithm) are required.

Josef Dick, Peter Kritzer, Gunther Leobacher et al.

QMC rules are equal weight quadrature rules for approximating integrals over $[0,1]^s$. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on $[0,1]^s$ with square integrable partial mixed derivatives of order $α$. Using Parseval's identity, this smoothness can be defined for all real numbers $α> 1/2$. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with $α$ arbitrarily close to $1/2$. To obtain such estimates we introduce a $\log$-scale for functions with smoothness close to $1/2$, which we call $\log$-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order $\mathcal{O}(N^{-1/2} (\log N)^{-μ(1-λ)/2})$ for any $1/μ<λ\le 1$, where $μ>1$ is a power in the $\log$-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights $(γ_j)_{j \in \mathbb{N}}$. It is known that if $\sum_{j=1}^\infty γ_j^τ< \infty$ for some $1/(2α) < τ\le 1$ one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where $τ$ is close to $1/(2 α)$, namely we show dimension independent error bounds under the condition that $\sum_{j=1}^\infty γ_j \max\{1, \log γ_j^{-1}\}^{μ(1-λ)} < \infty$ for some $1/μ< λ\le 1$. The essential tool in our analysis is a $\log$-scale Jensen's inequality. The results described above also apply to integration in $\log$-cosine spaces using tent-transformed lattice rules.