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

SIAM Journal on Numerical Analysis

On Korobov Lattice Rules in Weighted Spaces

Xiaoqun Wang, Ian H. Sloan, Josef Dick

Published Jan 1, 2004• 23 citations
Publisher

Abstract

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.

DOI
10.1137/s0036142903425021

Related papers

Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate

Josef Dick, Takashi Goda, Kosuke Suzuki

We study a randomized quadrature algorithm to approximate the integral of periodic functions defined over the high-dimensional unit cube. Recent work by Kritzer, Kuo, Nuyens and Ullrich [J. Approx. Theory 240 (2019), pp. 96–113] shows that rank-1 lattice rules with a randomly chosen number of points and good generating vector achieve almost the optimal order of the randomized error in weighted Korobov spaces, and moreover, that the error is bounded independently of the dimension if the weight parameters, γ j \gamma _j , satisfy the summability condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty , where α \alpha is a smoothness parameter. The argument is based on the existence result that at least half of the possible generating vectors yield almost the optimal order of the worst-case error in the same function spaces. In this paper we provide a component-by-component construction algorithm of such randomized rank-1 lattice rules, without any need to check whether the constructed generating vectors satisfy a desired worst-case error bound. Similarly to the above-mentioned work, we prove that our algorithm achieves almost the optimal order of the randomized error and that the error bound is independent of the dimension if the same condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty holds. We also provide analogous results for tent-transformed lattice rules for weighted half-period cosine spaces and for polynomial lattice rules in weighted Walsh spaces, respectively.

arXiv:2109.11694•Mathematics of Computation•Jun 15, 2022•11 citations

A randomized lattice rule without component-by-component construction

Takashi Goda

We study the multivariate integration problem for periodic functions from the weighted Korobov space in the randomized setting. We introduce a new randomized rank-1 lattice rule with a randomly chosen number of points, which avoids the need for component-by-component construction in the search for good generating vectors while still achieving nearly the optimal rate of the randomized error. Our idea is to exploit the fact that at least half of the possible generating vectors yield nearly the optimal rate of the worst-case error in the deterministic setting. By randomly choosing generating vectors r r times and comparing their corresponding worst-case errors, one can find one generating vector with a desired worst-case error bound with a very high probability, and the (small) failure probability can be controlled by increasing r r logarithmically as a function of the number of points. Numerical experiments are conducted to support our theoretical findings.

arXiv:2403.02660•Mathematics of Computation•Dec 3, 2024•5 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

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_{\infty}$ 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<α\le 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•Jan 28, 2026•0 citations

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

$$L_2$$-Approximation Using Median Lattice Algorithms

Zexin Pan, Peter Kritzer, Takashi Goda

Abstract In this paper, we study the problem of multivariate $$L_2$$ L 2 -approximation of functions belonging to a weighted Korobov space. We propose and analyze a median lattice-based algorithm, inspired by median integration rules, which have attracted significant attention in the theory of quasi-Monte Carlo methods. Our algorithm approximates the Fourier coefficients associated with a suitably chosen frequency index set, where each coefficient is estimated by taking the median over approximations from randomly shifted rank-1 lattice rules with independently chosen generating vectors. We prove that the algorithm achieves, with high probability, a convergence rate of the $$L_2$$ L 2 -approximation error that is arbitrarily close to optimal with respect to the number of function evaluations. Furthermore, we show that the error bound depends only polynomially on the dimension, or is even independent of the dimension, under certain summability conditions on the weights. Numerical experiments illustrate the performance of the proposed median lattice-based algorithm.

arXiv:2501.15331•Constructive Approximation•Jun 24, 2026•0 citations
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})(forarbitrary(for arbitrary(forarbitrary\delta ,{ > }, 0),withtheimpliedconstantdependingatworstpolynomiallyonthedimension.Here), with the implied constant depending at worst polynomially on the dimension. Here ),withtheimpliedconstantdependingatworstpolynomiallyonthedimension.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.
We study a randomized quadrature algorithm to approximate the integral of periodic functions defined over the high-dimensional unit cube. Recent work by Kritzer, Kuo, Nuyens and Ullrich [J. Approx. Theory 240 (2019), pp. 96–113] shows that rank-1 lattice rules with a randomly chosen number of points and good generating vector achieve almost the optimal order of the randomized error in weighted Korobov spaces, and moreover, that the error is bounded independently of the dimension if the weight parameters, γ j \gamma _j , satisfy the summability condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty , where α \alpha is a smoothness parameter. The argument is based on the existence result that at least half of the possible generating vectors yield almost the optimal order of the worst-case error in the same function spaces. In this paper we provide a component-by-component construction algorithm of such randomized rank-1 lattice rules, without any need to check whether the constructed generating vectors satisfy a desired worst-case error bound. Similarly to the above-mentioned work, we prove that our algorithm achieves almost the optimal order of the randomized error and that the error bound is independent of the dimension if the same condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty holds. We also provide analogous results for tent-transformed lattice rules for weighted half-period cosine spaces and for polynomial lattice rules in weighted Walsh spaces, respectively.
We study the multivariate integration problem for periodic functions from the weighted Korobov space in the randomized setting. We introduce a new randomized rank-1 lattice rule with a randomly chosen number of points, which avoids the need for component-by-component construction in the search for good generating vectors while still achieving nearly the optimal rate of the randomized error. Our idea is to exploit the fact that at least half of the possible generating vectors yield nearly the optimal rate of the worst-case error in the deterministic setting. By randomly choosing generating vectors r r times and comparing their corresponding worst-case errors, one can find one generating vector with a desired worst-case error bound with a very high probability, and the (small) failure probability can be controlled by increasing r r logarithmically as a function of the number of points. Numerical experiments are conducted to support our theoretical findings.
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.
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∞L_{\infty}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 111 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<α≤11/2<α\le 11/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α>1/2α>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 L2L_2L2​ error, while retaining the same tractability property.
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
L2L_2L2​-Approximation Using Median Lattice Algorithms
Abstract In this paper, we study the problem of multivariate L2L_2L2​ L 2 -approximation of functions belonging to a weighted Korobov space. We propose and analyze a median lattice-based algorithm, inspired by median integration rules, which have attracted significant attention in the theory of quasi-Monte Carlo methods. Our algorithm approximates the Fourier coefficients associated with a suitably chosen frequency index set, where each coefficient is estimated by taking the median over approximations from randomly shifted rank-1 lattice rules with independently chosen generating vectors. We prove that the algorithm achieves, with high probability, a convergence rate of the L2L_2L2​ L 2 -approximation error that is arbitrarily close to optimal with respect to the number of function evaluations. Furthermore, we show that the error bound depends only polynomially on the dimension, or is even independent of the dimension, under certain summability conditions on the weights. Numerical experiments illustrate the performance of the proposed median lattice-based algorithm.