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

Polynomial copy rules in Walsh spaces

Dirk Nuyens, Ronald F. A. Cools

Published Jun 1, 2008• 0 citations
OpenAlex

Abstract

In the 1990's copy rules have been studied as an easy and convenient way to construct lattice rules with a huge amount of points. Starting with the analysis of higher-rank lattice rules it was demonstrated numerically by Sloan and Walsh (1990) that copying scaled down rules by $\tfrac{1}{2}$ or $\tfrac{1}{3}$th to fill up the unit cube---conveniently only in the f irst few dimensions to avoid a curse of dimensionality by construction---could deliver rules which have a better worst -case error for the standard Korobov space than basic rank-$1$ rules. Further results were obtained by Disney and Sloan (1992), Joe and Sloan (1992) and Joe and Disney (1993). More recently, these results were extended to the product weighted Korobov space by Kuo and Joe (2003) in which condit ions on the weights were found to obtain a smaller worst-case error for an (intermediate) copy rule than for a rank-$1 $ rule. (Another recent track, called augmentation sequences, is investigated by Robinson, Li and Hill, but these are not directly relevant to this talk.) Here we present results on polynomial copy rules in a weighted Walsh space. We show some similarities with normal copy rules, as can be expected by the similarities between polynomial lattice rules and normal lattice rules, and some differences which show up in the theory. We derive an expression for the mean of the worst-case error and an existence theorem for polynomial copy rules which will do better than the mean follows from this. Comparing this mean to the mean of normal polynomial lattice rules, we can analyse when copying is expected to be favorable. We remark that, as is the case for normal copy rules, polynomial copy rules can also be constructed by the fast component-by-component construction algorithm.

Related papers

Constructions of copy rules

Dirk Nuyens, Ronald F. A. Cools, Theodore E. Simos +2 more

For some function classes it is known that using copies of a scaled down lattice rule can reduce the worst‐case error for numerical integration of functions from this class. In a slight generalization we show that it is possible to construct these so‐called “copy rules” by the fast component‐by‐component algorithm and review the conditions on when these rules would be preferable over normal lattice rules. We then present a generalization of copy rules to polynomial lattice rules and show similar results for the polynomial case as exist for the standard case of scalar lattice rules.

AIP conference proceedings•Jan 1, 2007•0 citations

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 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

The construction of good lattice rules and polynomial lattice rules

Dirk Nuyens

A comprehensive overview of lattice rules and polynomial lattice rules is given for function spaces based on $\ell_p$ semi-norms. Good lattice rules and polynomial lattice rules are defined as those obtaining worst-case errors bounded by the optimal rate of convergence for the function space. The focus is on algebraic rates of convergence $O(N^{-α+ε})$ for $α\ge 1$ and any $ε> 0$, where $α$ is the decay of a series representation of the integrand function. The dependence of the implied constant on the dimension can be controlled by weights which determine the influence of the different dimensions. Different types of weights are discussed. The construction of good lattice rules, and polynomial lattice rules, can be done using the same method for all $1 < p \le \infty$; but the case $p=1$ is special from the construction point of view. For $1 < p \le \infty$ the component-by-component construction and its fast algorithm for different weighted function spaces is then discussed.

arXiv:1308.3601•De Gruyter eBooks•Jul 25, 2014•46 citations

Lattice rules and beyond..

Dirk Nuyens

In this talk I will show the beautiful simplicity of approximating high-dimensional integrals using lattice rules. In current engineering applications it is relatively easy to come up with very high and ultra high dimensional integrals, which might be expectations, that depend on hundreds, thousands, or even an infinite number of variables. As the minimal non-trivial tensor product rule, constructed from a 2-point rule, in 100 dimensions already uses 2^{100} = 1267650600228229401496703205376 ≈ 10^{30} function evaluations—which would take 10^{24} seconds at 1 function evaluation per microsecond and we remember the age of the universe to be only approximately 10^{17} seconds—we all know why to use Monte Carlo or quasi-Monte Carlo methods where we can freely choose the number of function evaluations independent of the number of dimensions. While plain vanilla Monte Carlo methods are very robust and easy to apply, in the case of quasi-Monte Carlo methods a lot more details can pop up. I will first introduce the most elegant—in my biased opinion, which I will defend—of all quasi-Monte Carlo methods: the rank-1 lattice rule. This method is defined by one single integer generating vector together with the total number of points in the rule. Approximating a multivariate integral by this method can be done in one line of Matlab code! As one is often interested in successive approximations I will next introduce a rank-1 lattice sequence. Maybe surprisingly, also here, one simple line of Matlab code is sufficient to calculate a segment of a lattice sequence (with a special property). While for Monte Carlo integration the usual assumption is L2 integrability, leading to an error bound of O(N^{−1/2}). For quasi-Monte Carlo methods we generally work with more involved function space settings, leading to error bounds of the form O(N^{−α}) with α ≥ 1/2. I will show the standard function space settings and dive into the weighted function spaces which are being used in current theory to be able to make the error bounds independent of the number of dimensions. We will gloss over the Korobov space of periodic smooth functions, the unanchored Sobolev space with first mixed derivatives, and the cosine space which is a special space of smooth non-periodic functions. All of which are spaces of so-called mixed dominating smoothness, which in terms of mixed derivatives would mean ∂^{k_1+···+k_s} /(∂x_1^{k_1} · · · ∂x_s^{k_s}) exists for all (k_1, . . . , k_s) ≤ (α, . . . , α). For non-periodic function spaces lattice rules and sequences can only reach O(N^{−1}) convergence. To arrive at higher-order convergence of O(N^{−α}) for non-periodic functions we dive into higher-order Sobolev spaces (of mixed dominating smoothness) in combination with digital nets, but here disguised as a lattice rule, namely polynomial lattice rules. Here, all arithmetic is over a finite field (we will choose the one of order 2) and our lattice rules now take the form of a lattice of polynomials which we map back to points in the unit cube. Higher order can now be obtained by means of the interlacing method from Josef Dick. Although more complicated, again, given the generating matrices of the digital net (as a bunch of integers), and two lines for a magical de Bruijn sequence, we can approximate an integral by such a digital sequence with a single line of (complicated) Matlab code. While Matlab/Octave one-liners might be fun, and somehow instructive, I will also point you to my online resources where code is available to (a) construct good lattice rules, lattice sequences and polynomial lattice rules (for product, order-dependent, product-and-order-dependent aka POD, and smoothness-driven product-and-order dependent aka SPOD) weighted spaces, and (b) generate points given the generating vector or matrices. Armed with this software you will be able to attack your own problems in no time. This talk is based upon the results of collaborations with many colleagues.

•Aug 1, 2016•0 citations

Constructive approaches to quasi-Monte Carlo methods for multiple integration

Frances Y. Kuo

Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.

•Jan 1, 2002•2 citations
In the 1990's copy rules have been studied as an easy and convenient way to construct lattice rules with a huge amount of points. Starting with the analysis of higher-rank lattice rules it was demonstrated numerically by Sloan and Walsh (1990) that copying scaled down rules by 12\tfrac{1}{2}21​ or 13\tfrac{1}{3}31​th to fill up the unit cube---conveniently only in the f irst few dimensions to avoid a curse of dimensionality by construction---could deliver rules which have a better worst -case error for the standard Korobov space than basic rank-111 rules. Further results were obtained by Disney and Sloan (1992), Joe and Sloan (1992) and Joe and Disney (1993). More recently, these results were extended to the product weighted Korobov space by Kuo and Joe (2003) in which condit ions on the weights were found to obtain a smaller worst-case error for an (intermediate) copy rule than for a rank-11 1 rule. (Another recent track, called augmentation sequences, is investigated by Robinson, Li and Hill, but these are not directly relevant to this talk.) Here we present results on polynomial copy rules in a weighted Walsh space. We show some similarities with normal copy rules, as can be expected by the similarities between polynomial lattice rules and normal lattice rules, and some differences which show up in the theory. We derive an expression for the mean of the worst-case error and an existence theorem for polynomial copy rules which will do better than the mean follows from this. Comparing this mean to the mean of normal polynomial lattice rules, we can analyse when copying is expected to be favorable. We remark that, as is the case for normal copy rules, polynomial copy rules can also be constructed by the fast component-by-component construction algorithm.
For some function classes it is known that using copies of a scaled down lattice rule can reduce the worst‐case error for numerical integration of functions from this class. In a slight generalization we show that it is possible to construct these so‐called “copy rules” by the fast component‐by‐component algorithm and review the conditions on when these rules would be preferable over normal lattice rules. We then present a generalization of copy rules to polynomial lattice rules and show similar results for the polynomial case as exist for the standard case of scalar lattice rules.
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.
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.
A comprehensive overview of lattice rules and polynomial lattice rules is given for function spaces based on ℓp\ell_pℓp​ semi-norms. Good lattice rules and polynomial lattice rules are defined as those obtaining worst-case errors bounded by the optimal rate of convergence for the function space. The focus is on algebraic rates of convergence O(N−α+ε)O(N^{-α+ε})O(N−α+ε) for α≥1α\ge 1α≥1 and any ε>0ε> 0ε>0, where ααα is the decay of a series representation of the integrand function. The dependence of the implied constant on the dimension can be controlled by weights which determine the influence of the different dimensions. Different types of weights are discussed. The construction of good lattice rules, and polynomial lattice rules, can be done using the same method for all 1<p≤∞1 < p \le \infty1<p≤∞; but the case p=1p=1p=1 is special from the construction point of view. For 1<p≤∞1 < p \le \infty1<p≤∞ the component-by-component construction and its fast algorithm for different weighted function spaces is then discussed.
In this talk I will show the beautiful simplicity of approximating high-dimensional integrals using lattice rules. In current engineering applications it is relatively easy to come up with very high and ultra high dimensional integrals, which might be expectations, that depend on hundreds, thousands, or even an infinite number of variables. As the minimal non-trivial tensor product rule, constructed from a 2-point rule, in 100 dimensions already uses 2^{100} = 1267650600228229401496703205376 ≈ 10^{30} function evaluations—which would take 10^{24} seconds at 1 function evaluation per microsecond and we remember the age of the universe to be only approximately 10^{17} seconds—we all know why to use Monte Carlo or quasi-Monte Carlo methods where we can freely choose the number of function evaluations independent of the number of dimensions. While plain vanilla Monte Carlo methods are very robust and easy to apply, in the case of quasi-Monte Carlo methods a lot more details can pop up. I will first introduce the most elegant—in my biased opinion, which I will defend—of all quasi-Monte Carlo methods: the rank-1 lattice rule. This method is defined by one single integer generating vector together with the total number of points in the rule. Approximating a multivariate integral by this method can be done in one line of Matlab code! As one is often interested in successive approximations I will next introduce a rank-1 lattice sequence. Maybe surprisingly, also here, one simple line of Matlab code is sufficient to calculate a segment of a lattice sequence (with a special property). While for Monte Carlo integration the usual assumption is L2 integrability, leading to an error bound of O(N^{−1/2}). For quasi-Monte Carlo methods we generally work with more involved function space settings, leading to error bounds of the form O(N^{−α}) with α ≥ 1/2. I will show the standard function space settings and dive into the weighted function spaces which are being used in current theory to be able to make the error bounds independent of the number of dimensions. We will gloss over the Korobov space of periodic smooth functions, the unanchored Sobolev space with first mixed derivatives, and the cosine space which is a special space of smooth non-periodic functions. All of which are spaces of so-called mixed dominating smoothness, which in terms of mixed derivatives would mean ∂^{k_1+···+k_s} /(∂x_1^{k_1} · · · ∂x_s^{k_s}) exists for all (k_1, . . . , k_s) ≤ (α, . . . , α). For non-periodic function spaces lattice rules and sequences can only reach O(N^{−1}) convergence. To arrive at higher-order convergence of O(N^{−α}) for non-periodic functions we dive into higher-order Sobolev spaces (of mixed dominating smoothness) in combination with digital nets, but here disguised as a lattice rule, namely polynomial lattice rules. Here, all arithmetic is over a finite field (we will choose the one of order 2) and our lattice rules now take the form of a lattice of polynomials which we map back to points in the unit cube. Higher order can now be obtained by means of the interlacing method from Josef Dick. Although more complicated, again, given the generating matrices of the digital net (as a bunch of integers), and two lines for a magical de Bruijn sequence, we can approximate an integral by such a digital sequence with a single line of (complicated) Matlab code. While Matlab/Octave one-liners might be fun, and somehow instructive, I will also point you to my online resources where code is available to (a) construct good lattice rules, lattice sequences and polynomial lattice rules (for product, order-dependent, product-and-order-dependent aka POD, and smoothness-driven product-and-order dependent aka SPOD) weighted spaces, and (b) generate points given the generating vector or matrices. Armed with this software you will be able to attack your own problems in no time. This talk is based upon the results of collaborations with many colleagues.
Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.