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•50 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•2 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

Tractability of multivariate analytic problems

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which $s$-variate problems can be approximated to within $\varepsilon$ by using, say, polynomially many in $s$ and $\varepsilon^{-1}$ function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with $\varepsilon^{-1}$ replaced by $1+\log \varepsilon^{-1}$. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of $s$ and $1+\log \varepsilon^{-1}$. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.

arXiv:1407.1615•De Gruyter eBooks•Jul 25, 2014•22 citations

A note on approximation in weighted Korobov spaces via multiple rank-1 lattices

Mou Cai, Takashi Goda

This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the L ∞ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter α to be greater than 1 and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where 1 / 2 < α ≤ 1 and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any α > 1 / 2 . Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared L 2 error, while retaining the same tractability property.

arXiv:2601.20290•Journal of Complexity•May 12, 2026•4 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.
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.
In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which sss-variate problems can be approximated to within ε\varepsilonε by using, say, polynomially many in sss and ε−1\varepsilon^{-1}ε−1 function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with ε−1\varepsilon^{-1}ε−1 replaced by 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of sss and 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.
This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the L ∞ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter α to be greater than 1 and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where 1 / 2 < α ≤ 1 and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any α > 1 / 2 . Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared L 2 error, while retaining the same tractability property.