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

AIP conference proceedings

Constructions of copy rules

Dirk Nuyens, Ronald F. A. Cools, Theodore E. Simos, George Psihoyios, Ch. Tsitouras

Published Jan 1, 2007• 0 citations
Publisher

Abstract

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.

DOI
10.1063/1.2790108

Related papers

Polynomial copy rules in Walsh spaces

Dirk Nuyens, Ronald F. A. Cools

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.

•Jun 1, 2008•0 citations

On a projection-corrected component-by-component construction

Josef Dick, Peter Kritzer

The component-by-component construction is the standard method of finding good lattice rules or polynomial lattice rules for numerical integration. Several authors have reported that in numerical experiments the generating vector sometimes has repeated components. We study a variation of the classical component-by-component algorithm for the construction of lattice or polynomial lattice point sets where the components are forced to differ from each other. This avoids the problem of having projections where all quadrature points lie on the main diagonal. Since the previous results on the worst-case error do not apply to this modified algorithm, we prove such an error bound here. We also discuss further restrictions on the choice of components in the component-by-component algorithm.

arXiv:1502.04396•Feb 16, 2015•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

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

Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

Jan F. Baldeaux, Josef Dick, Gunther Leobacher +2 more

arXiv:1105.2599•Numerical Algorithms•Sep 3, 2011•56 citations

Construction of lattice rules for multiple integration based on a weighted discrepancy

Vasile Sinescu

High-dimensional integrals arise in a variety of areas, including quantum physics, the physics and chemistry of molecules, statistical mechanics and more recently, in financial applications. In order to approximate multidimensional integrals, one may use Monte Carlo methods in which the quadrature points are generated randomly or quasi-Monte Carlo methods, in which points are generated deterministically. One particular class of quasi-Monte Carlo methods for multivariate integration is represented by lattice rules. Lattice rules constructed throughout this thesis allow good approximations to integrals of functions belonging to certain weighted function spaces. These function spaces were proposed as an explanation as to why integrals in many variables appear to be successfully approximated although the standard theory indicates that the number of quadrature points required for reasonable accuracy would be astronomical because of the large number of variables. The purpose of this thesis is to contribute to theoretical results regarding the construction of lattice rules for multiple integration. We consider both lattice rules for integrals over the unit cube and lattice rules suitable for integrals over Euclidean space. The research reported throughout the thesis is devoted to finding the generating vector required to produce lattice rules that have what is termed a low weighted discrepancy . In simple terms, the discrepancy is a measure of the uniformity of the distribution of the quadrature points or in other settings, a worst-case error. One of the assumptions used in these weighted function spaces is that variables are arranged in the decreasing order of their importance and the assignment of weights in this situation results in so-called product weights . In other applications it is rather the importance of group of variables that matters. This situation is modelled by using function spaces in which the weights are general . In the weighted settings mentioned above, the quality of the lattice rules is assessed by the weighted discrepancy mentioned earlier. Under appropriate conditions on the weights, the lattice rules constructed here produce a convergence rate of the error that ranges from O(n−1/2) to the (believed) optimal O(n−1+δ) for any δ gt 0, with the involved constant independent of the dimension.

•Jan 1, 2008•0 citations
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.
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-$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.
The component-by-component construction is the standard method of finding good lattice rules or polynomial lattice rules for numerical integration. Several authors have reported that in numerical experiments the generating vector sometimes has repeated components. We study a variation of the classical component-by-component algorithm for the construction of lattice or polynomial lattice point sets where the components are forced to differ from each other. This avoids the problem of having projections where all quadrature points lie on the main diagonal. Since the previous results on the worst-case error do not apply to this modified algorithm, we prove such an error bound here. We also discuss further restrictions on the choice of components in the component-by-component algorithm.
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.
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.
High-dimensional integrals arise in a variety of areas, including quantum physics, the physics and chemistry of molecules, statistical mechanics and more recently, in financial applications. In order to approximate multidimensional integrals, one may use Monte Carlo methods in which the quadrature points are generated randomly or quasi-Monte Carlo methods, in which points are generated deterministically. One particular class of quasi-Monte Carlo methods for multivariate integration is represented by lattice rules. Lattice rules constructed throughout this thesis allow good approximations to integrals of functions belonging to certain weighted function spaces. These function spaces were proposed as an explanation as to why integrals in many variables appear to be successfully approximated although the standard theory indicates that the number of quadrature points required for reasonable accuracy would be astronomical because of the large number of variables. The purpose of this thesis is to contribute to theoretical results regarding the construction of lattice rules for multiple integration. We consider both lattice rules for integrals over the unit cube and lattice rules suitable for integrals over Euclidean space. The research reported throughout the thesis is devoted to finding the generating vector required to produce lattice rules that have what is termed a low weighted discrepancy . In simple terms, the discrepancy is a measure of the uniformity of the distribution of the quadrature points or in other settings, a worst-case error. One of the assumptions used in these weighted function spaces is that variables are arranged in the decreasing order of their importance and the assignment of weights in this situation results in so-called product weights . In other applications it is rather the importance of group of variables that matters. This situation is modelled by using function spaces in which the weights are general . In the weighted settings mentioned above, the quality of the lattice rules is assessed by the weighted discrepancy mentioned earlier. Under appropriate conditions on the weights, the lattice rules constructed here produce a convergence rate of the error that ranges from O(n−1/2) to the (believed) optimal O(n−1+δ) for any δ gt 0, with the involved constant independent of the dimension.