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

Exponential convergence and tractability of multivariate integration for Korobov spaces

Josef Dick, Gerhard Larcher, Friedrich Pillichshammer, Henryk Woźniakowski

Published Nov 2, 2010• 55 citations
Publisher

Abstract

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.

DOI
10.1090/s0025-5718-2010-02433-0

Related papers

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

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

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

Mathematics of Computation•Nov 20, 2013•44 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

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

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

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

Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers

Erich Novak, Ian H. Sloan, H. Woźniakowski

The paper studies quantum complexity, tractability, and strong tractability for high dimensional multivariate approximation. We study a space of functions important in many applications. A function space is weighted if certain variables are more important than others; the weights show the relative importance of the variables. In an unweighted space all variables are equally important and multivariate approximation is intractable. We want to study when the complexity of multivariate approximation is independent of the number of variables and depends polynomially on 1/E. The main conclusions are: Multivariate approximation on a quantum computer can be solved roughly (1/E)^(1+r) times faster than on a classical computer using randomization. Here, r is a positive parameter that depends on the weights and may be large. This means that the speed-up of quantum over classical computers may be much larger than quadratic. Multivariate approximation on a quantum computer is exponentially faster than on a classical computer with a worst case assurance even if the sum of weights is infinite but a certain power of them is finite. We have designed a quantum algorithm with error at most E that uses about d+log(1/E) qubits. Hence, we have only linear dependence on the dimension d and logarithmic dependence on 1/E. Therefore, for some applications the number of qubits is quite modest.

arXiv:quant-ph/0206023•Jun 4, 2002•0 citations
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.
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
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 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.
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.
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.
The paper studies quantum complexity, tractability, and strong tractability for high dimensional multivariate approximation. We study a space of functions important in many applications. A function space is weighted if certain variables are more important than others; the weights show the relative importance of the variables. In an unweighted space all variables are equally important and multivariate approximation is intractable. We want to study when the complexity of multivariate approximation is independent of the number of variables and depends polynomially on 1/E. The main conclusions are: Multivariate approximation on a quantum computer can be solved roughly (1/E)^(1+r) times faster than on a classical computer using randomization. Here, r is a positive parameter that depends on the weights and may be large. This means that the speed-up of quantum over classical computers may be much larger than quadratic. Multivariate approximation on a quantum computer is exponentially faster than on a classical computer with a worst case assurance even if the sum of weights is infinite but a certain power of them is finite. We have designed a quantum algorithm with error at most E that uses about d+log(1/E) qubits. Hence, we have only linear dependence on the dimension d and logarithmic dependence on 1/E. Therefore, for some applications the number of qubits is quite modest.