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

arXiv:1308.3601 · De Gruyter eBooks

The construction of good lattice rules and polynomial lattice rules

Dirk Nuyens

Published Jul 25, 2014• 46 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1515/9783110317930.223

Related papers

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

Richardson Extrapolation of Polynomial Lattice Rules

Josef Dick, Takashi Goda, Takehito Yoshiki

We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness $\alpha\geq 2$ defined over the $s$-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the extrapolated polynomial lattice rule, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: (i) construction of classical polynomial lattice rules over $\Bbb{F}_b$ with $\alpha$ consecutive sizes of nodes, $b^{m-\alpha+1},\ldots,b^{m}$, and (ii) recursive application of Richardson extrapolation to a chain of $\alpha$ approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order $(s+\alpha)N\log N$, which improves the currently known result for the interlaced polynomial lattice rule, which is of order $s\alpha N\log N$. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.

arXiv:1707.03989•SIAM Journal on Numerical Analysis•Jan 1, 2019•11 citations

A gentle introduction to approximating high-dimensional integrals with lattice rules and a maybe-not-so-gentle introduction to the relevant function spaces for QMC integration

Dirk Nuyens

These lecture notes give both a practical and theoretical introduction to high-dimensional integration with lattice rules. We introduce lattice points and rules in combination with accompanying Julia code. Next we introduce the typical function spaces used in the literature. We compare classical Sobolev spaces with Sobolev spaces of dominating mixed smoothness. We derive lower bounds and show that the curse of dimensionality is unavoidable for these unweighted function spaces. Next we switch to weighted periodic spaces and derive a constructive upper bound using the component-by-component construction for the generating vector of a lattice rule. We pick periodic spaces because they are a perfect match with lattice rules. The upper bound shows that under suitable conditions on the weights we obtain dimension-independent worst-case error bounds. We then use embedding constants to transfer these bounds to some common norms for these periodic spaces.

arXiv:2610.25331•Oct 18, 2026•0 citations

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

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

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
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.
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.
We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness α≥2\alpha\geq 2α≥2 defined over the sss-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the extrapolated polynomial lattice rule, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: (i) construction of classical polynomial lattice rules over Fb\Bbb{F}_bFb​ with α\alphaα consecutive sizes of nodes, bm−α+1,…,bmb^{m-\alpha+1},\ldots,b^{m}bm−α+1,…,bm, and (ii) recursive application of Richardson extrapolation to a chain of α\alphaα approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order (s+α)Nlog⁡N(s+\alpha)N\log N(s+α)NlogN, which improves the currently known result for the interlaced polynomial lattice rule, which is of order sαNlog⁡Ns\alpha N\log NsαNlogN. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.
These lecture notes give both a practical and theoretical introduction to high-dimensional integration with lattice rules. We introduce lattice points and rules in combination with accompanying Julia code. Next we introduce the typical function spaces used in the literature. We compare classical Sobolev spaces with Sobolev spaces of dominating mixed smoothness. We derive lower bounds and show that the curse of dimensionality is unavoidable for these unweighted function spaces. Next we switch to weighted periodic spaces and derive a constructive upper bound using the component-by-component construction for the generating vector of a lattice rule. We pick periodic spaces because they are a perfect match with lattice rules. The upper bound shows that under suitable conditions on the weights we obtain dimension-independent worst-case error bounds. We then use embedding constants to transfer these bounds to some common norms for these periodic spaces.
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.
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.