Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Mathematics of Computation

Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

Published Nov 20, 2013• 44 citations
Publisher

Abstract

We study multivariate integration for a weighted Korobov space of periodic infinitely many times differentiable functions for which the Fourier coefficients decay exponentially fast. The weights are defined in terms of two non-decreasing sequences a = { a i } \mathbf {a}=\{a_i\} and b = { b i } \mathbf {b}=\{b_i\} of numbers no less than one and a parameter ω ∈ ( 0 , 1 ) \omega \in (0,1) . Let e ( n , s ) e(n,s) be the minimal worst-case error of all algorithms that use n n function values in the s s -variate case. We would like to check conditions on a \mathbf {a} , b \mathbf {b} and ω \omega such that e ( n , s ) e(n,s) decays exponentially fast, i.e., for some q ∈ ( 0 , 1 ) q\in (0,1) and p > 0 p>0 we have

DOI
10.1090/s0025-5718-2013-02739-1

Related papers

Exponential convergence and tractability of multivariate integration for Korobov spaces

Josef Dick, Gerhard Larcher, Friedrich Pillichshammer +1 more

In this paper we study multivariate integration for a weighted Korobov space for which the Fourier coefficients of the functions decay exponentially fast. This implies that the functions of this space are infinitely times differentiable. Weights of the Korobov space monitor the influence of each variable and each group of variables. We show that there are numerical integration rules which achieve an exponential convergence of the worst-case integration error. We also investigate the dependence of the worst-case error on the number of variables s s , and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on s s is never exponential, and sometimes the dependence on s s is polynomial or there is no dependence on s s at all.

Mathematics of Computation•Nov 2, 2010•55 citations

$\boldsymbol{L}_{\infty}$-approximation in Korobov spaces with Exponential Weights

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

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 $Λ$.

arXiv:1602.02572•Feb 8, 2016•0 citations

Approximation of analytic functions in Korobov spaces

Josef Dick, Peter Kritzer, Friedrich Pillichshammer +1 more

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.

arXiv:1211.5822•Nov 25, 2012•0 citations

A note on Korobov lattice rules for integration of analytic functions

Friedrich Pillichshammer

We study numerical integration for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. In particular, we are interested in how the error depends on the dimension d. Many recent papers deal with this problem or similar problems and provide matching necessary and sufficient conditions for various notions of tractability. In most cases even simple algorithms are known which allow to achieve these notions of tractability. However, there is a gap in the literature: while for the notion of exponential-weak tractability one knows matching necessary and sufficient conditions, so far no explicit algorithm has been known which yields the desired result. In this paper we close this gap and prove that Korobov lattice rules are suitable algorithms in order to achieve exponential-weak tractability for integration in weighted Korobov spaces of analytic periodic functions.

arXiv:2010.03286•Journal of Complexity•Oct 10, 2020•0 citations

Exponential convergence for integration over R^s

Dong Nguyen, Dirk Nuyens

In this talk we study multivariate integration over R^s for weighted function space of infinitely many times differentiable functions for which the Fourier transform decays exponentially fast. The weights allows us to define the different influence of each variables. We prove that we can achieve the exponential convergence rate using a classical quasi-Monte Carlo method. More specific, we prove two convergence rates of $\mathcal{O}(e^{-N^{\frac{1}{D+B}}})$ and $\mathcal{O} (e^{-\frac{N^{\frac{1}{B}}}{\ln^{\frac{1}{D}} N}})$, where D and B are respectively defined by the exponential decay of the Fourier coefficients and of the integrand, for two different function spaces. We also show some numerical results that prove our theorems.

•Jul 1, 2015•0 citations

On Korobov Lattice Rules in Weighted Spaces

Xiaoqun Wang, Ian H. Sloan, Josef Dick

This paper studies the error bounds of multivariate integration in weighted function spaces using lattice rules of the Korobov form, in which the generating vector for an n-point rule with n prime has the form (1,a,...,a d -1 ) (mod,n). With the parameter a chosen optimally, we establish new error bounds for Korobov lattice rules in weighted Korobov spaces. In particular, we prove that if the weights decay sufficiently fast, the optimal Korobov lattice rule has an error bound of order O(n^{-\alpha/2 +\delta})$ (for arbitrary $\delta \,{ > }\, 0$), with the implied constant depending at worst polynomially on the dimension. Here $\alpha \,{ > }\,1$ is the smoothness parameter of the weighted Korobov spaces. We generalize the construction to the case where n is a product of arbitrary distinct prime numbers, with the purpose of reducing the construction cost without sacrificing much of the quality of the lattice rules. A corresponding result is deduced for weighted Sobolev spaces of nonperiodic functions, using randomly shifted optimal Korobov lattice rules. A comparison of the worst-case errors for Korobov lattice rules and the recent component-by-component constructions is presented. The investigation establishes the usefulness of (shifted) optimal Korobov lattice rules for integration, even in high dimensions, if the weights which characterize the weighted spaces are suitably chosen.

SIAM Journal on Numerical Analysis•Jan 1, 2004•23 citations
We study multivariate integration for a weighted Korobov space of periodic infinitely many times differentiable functions for which the Fourier coefficients decay exponentially fast. The weights are defined in terms of two non-decreasing sequences a = { a i } \mathbf {a}={a_i} and b = { b i } \mathbf {b}={b_i} of numbers no less than one and a parameter ω ∈ ( 0 , 1 ) \omega \in (0,1) . Let e ( n , s ) e(n,s) be the minimal worst-case error of all algorithms that use n n function values in the s s -variate case. We would like to check conditions on a \mathbf {a} , b \mathbf {b} and ω \omega such that e ( n , s ) e(n,s) decays exponentially fast, i.e., for some q ∈ ( 0 , 1 ) q\in (0,1) and p > 0 p>0 we have
In this paper we study multivariate integration for a weighted Korobov space for which the Fourier coefficients of the functions decay exponentially fast. This implies that the functions of this space are infinitely times differentiable. Weights of the Korobov space monitor the influence of each variable and each group of variables. We show that there are numerical integration rules which achieve an exponential convergence of the worst-case integration error. We also investigate the dependence of the worst-case error on the number of variables s s , and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on s s is never exponential, and sometimes the dependence on s s is polynomial or there is no dependence on s s at all.
L∞\boldsymbol{L}_{\infty}L∞​-approximation in Korobov spaces with Exponential Weights
We study multivariate L∞\boldsymbol{L}_{\infty}L∞​-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 a={aj}\boldsymbol{a}=\{a_j\}a={aj​} and b={bj}\boldsymbol{b}=\{b_j\}b={bj​} of positive real numbers bounded away from zero. We study the minimal worst-case error eL∞−app,Λ(n,s)e^{\boldsymbol{L}_{\infty}\mathrm{-app},Λ}(n,s)eL∞​−app,Λ(n,s) of all algorithms that use nnn information evaluations from a class ΛΛΛ in the sss-variate case. We consider two classes ΛΛΛ in this paper: the class ΛallΛ^{\rm all}Λall of all linear functionals and the class ΛstdΛ^{\rm std}Λstd of only function evaluations. We study exponential convergence of the minimal worst-case error, which means that eL∞−app,Λ(n,s)e^{\boldsymbol{L}_{\infty}\mathrm{-app},Λ}(n,s)eL∞​−app,Λ(n,s) converges to zero exponentially fast with increasing nnn. Furthermore, we consider how the error depends on the dimension sss. 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 sss and 1+log⁡ ε−11+\log\,\varepsilon^{-1}1+logε−1 to compute an ε\varepsilonε-approximation. We derive necessary and sufficient conditions on the sequences a\boldsymbol{a}a and b\boldsymbol{b}b for obtaining exponential error convergence, and also for obtaining the various notions of tractability. The results are the same for both classes ΛΛΛ.
We study multivariate L2L_2L2​-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 a={aj}\boldsymbol{a} =\{a_j\}a={aj​} and b={bj}\boldsymbol{b} =\{b_j\}b={bj​} of numbers no less than one. Let eL2−app,Λ(n,s)e^{L_2-\mathrm{app},Λ}(n,s)eL2​−app,Λ(n,s) be the minimal worst-case error of all algorithms that use nnn information functionals from the class ΛΛΛ in the sss-variate case. We consider two classes ΛΛΛ: the class ΛallΛ^{\rm all}Λall consists of all linear functionals and the class ΛstdΛ^{\rm std}Λstd consists of only function valuations. We study (EXP) exponential convergence. This means that eL2−app,Λ(n,s)≤C(s) q (n/C1(s))p(s)foralln,s∈N 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} eL2​−app,Λ(n,s)≤C(s)q(n/C1​(s))p(s)foralln,s∈N where q∈(0,1)q\in(0,1)q∈(0,1), and C,C1,p:N→(0,∞)C,C_1,p:\mathbb{N} \rightarrow (0,\infty)C,C1​,p:N→(0,∞). If we can take p(s)=p>0p(s)=p>0p(s)=p>0 for all sss 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 nnn 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,τ2c,τ_1,τ_2c,τ1​,τ2​ such that $n(\e,s)\le cs^{τ_1}(1+\log\,\e^{-1})^{τ_2}$ for all sss and $\e\in(0,1)$, and finally SPT holds iff the last estimate holds for τ1=0τ_1=0τ1​=0. The infimum of τ2τ_2τ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.
We study numerical integration for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. In particular, we are interested in how the error depends on the dimension d. Many recent papers deal with this problem or similar problems and provide matching necessary and sufficient conditions for various notions of tractability. In most cases even simple algorithms are known which allow to achieve these notions of tractability. However, there is a gap in the literature: while for the notion of exponential-weak tractability one knows matching necessary and sufficient conditions, so far no explicit algorithm has been known which yields the desired result. In this paper we close this gap and prove that Korobov lattice rules are suitable algorithms in order to achieve exponential-weak tractability for integration in weighted Korobov spaces of analytic periodic functions.
In this talk we study multivariate integration over R^s for weighted function space of infinitely many times differentiable functions for which the Fourier transform decays exponentially fast. The weights allows us to define the different influence of each variables. We prove that we can achieve the exponential convergence rate using a classical quasi-Monte Carlo method. More specific, we prove two convergence rates of O(e−N1D+B)\mathcal{O}(e^{-N^{\frac{1}{D+B}}})O(e−ND+B1​) and O(e−N1Bln⁡1DN)\mathcal{O} (e^{-\frac{N^{\frac{1}{B}}}{\ln^{\frac{1}{D}} N}})O(e−lnD1​NNB1​​), where D and B are respectively defined by the exponential decay of the Fourier coefficients and of the integrand, for two different function spaces. We also show some numerical results that prove our theorems.
This paper studies the error bounds of multivariate integration in weighted function spaces using lattice rules of the Korobov form, in which the generating vector for an n-point rule with n prime has the form (1,a,...,a d -1 ) (mod,n). With the parameter a chosen optimally, we establish new error bounds for Korobov lattice rules in weighted Korobov spaces. In particular, we prove that if the weights decay sufficiently fast, the optimal Korobov lattice rule has an error bound of order O(n^{-\alpha/2 +\delta})$ (for arbitrary δ > 0\delta \,{ > }\, 0δ>0), with the implied constant depending at worst polynomially on the dimension. Here α > 1\alpha \,{ > }\,1α>1 is the smoothness parameter of the weighted Korobov spaces. We generalize the construction to the case where n is a product of arbitrary distinct prime numbers, with the purpose of reducing the construction cost without sacrificing much of the quality of the lattice rules. A corresponding result is deduced for weighted Sobolev spaces of nonperiodic functions, using randomly shifted optimal Korobov lattice rules. A comparison of the worst-case errors for Korobov lattice rules and the recent component-by-component constructions is presented. The investigation establishes the usefulness of (shifted) optimal Korobov lattice rules for integration, even in high dimensions, if the weights which characterize the weighted spaces are suitably chosen.