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

Constructing Randomly Shifted Lattice Rules in Weighted Sobolev Spaces

Ian H. Sloan, Frances Y. Kuo, Stephen Joe

Published Jan 1, 2002• 134 citations
Publisher

Abstract

Shifted rank-1 lattice rules, a special class of quasi-Monte Carlo methods, have recently been proposed by the present authors for the integration of functions belonging to certain "weighted" Sobolev spaces. The shifts in these rules were generated in a deterministic manner. In contrast, in this paper we generate these shifts randomly. This allows probabilistic estimates for the error in a given integral. It also reduces the number of operations required to find the generating vectors for the underlying lattice rules component-by-component. The rules thus constructed achieve a worst-case strong tractability error bound in an average or probabilistic sense.

DOI
10.1137/s0036142901393942

Related papers

On the step-by-step construction of quasi–Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces

Ian H. Sloan, Frances Y. Kuo, Stephen Joe

We develop and justify an algorithm for the construction of quasi–Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found “component-by-component”: the ( d + 1 d+1 )-th component of the generator vector and the shift are obtained by successive 1 1 -dimensional searches, with the previous d d components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for n n -point rules with n n prime and all dimensions 1 to d d requires a total cost of O ( n 3 d 2 ) O(n^3d^2) operations. This may be reduced to O ( n 3 d ) O(n^3d) operations at the expense of O ( n 2 ) O(n^2) storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and n n up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.

Mathematics of Computation•Mar 20, 2002•91 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

A note on unshifted lattice rules for high-dimensional integration in weighted unanchored Sobolev spaces

Takashi Goda

This short article studies a deterministic quasi-Monte Carlo lattice rule in weighted unanchored Sobolev spaces of smoothness 1 . Building on the error analysis by Kazashi and Sloan, we prove the existence of unshifted rank-1 lattice rules that achieve a worst-case error of O ( n − 1 / 4 ( log n ) 1 / 2 ) , with the implied constant independent of the dimension, under certain summability conditions on the weights. Although this convergence rate is inferior to the one achievable for the shifted-averaged root mean squared worst-case error, the result does not rely on random shifting or transformation and holds unconditionally without any conjecture, in contrast to the result of Kazashi and Sloan.

arXiv:2504.14768•Applied Mathematics Letters•May 28, 2025•1 citation

ON THE COMPONENT BY COMPONENT CONSTRUCTION OF POLYNOMIAL LATTICE POINT SETS FOR NUMERICAL INTEGRATION IN WEIGHTED SOBOLEV SPACES

Peter Kritzer, Friedrich Pillichshammer

Polynomial lattice point sets are polynomial versions of classical lattice point sets and among the most widely used classes of node sets for quasi- Monte Carlo integration. In this paper, we study the worst-case integration error of digitally shifted polynomial lattice point sets and give step by step construction algorithms to obtain polynomial lattices that achieve a low worst-case error in certain weighted Sobolev spaces. The construction algorithm is a so-called com- ponent by component algorithm, choosing one component of the relevant point set at a time. Furthermore, under certain conditions on the weights, we achieve that there is only a polynomial or even no dependence of the worst-case error on the dimension of the integration problem.

•Jan 1, 2011•3 citations

Open type quasi-Monte Carlo integration based on Halton sequences in weighted Sobolev spaces

Peter Hellekalek, Peter Kritzer, Friedrich Pillichshammer

In this paper, we study quasi-Monte Carlo (QMC) integration in weighted Sobolev spaces. In contrast to many previous results the QMC algorithms considered here are of open type, i.e., they are extensible in the number of sample points without having to discard the samples already used. As the underlying integration nodes we consider randomized Halton sequences in prime bases $\boldsymbol{p}=(p_1,...,p_s)$ for which we study the root mean square (RMS) worst-case error. The randomization method is a $\boldsymbol{p}$-adic shift which is based on $\boldsymbol{p}$-adic arithmetic. The obtained error bounds are optimal in the order of magnitude of the number of sample nodes. Furthermore we obtain conditions on the coordinate weights under which the error bounds are independent of the dimension $s$. In terms of the field of Information-Based Complexity this means that the corresponding QMC rule achieves a strong polynomial tractability error bound. Our findings on the RMS worst-case error of randomized Halton sequences can be carried over to the RMS $L_2$-discrepancy. Except for the $\boldsymbol{p}$-adic shift our results are fully constructive and no search algorithms (such as the component-by-component algorithm) are required.

arXiv:1411.3823•Nov 14, 2014•0 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
Shifted rank-1 lattice rules, a special class of quasi-Monte Carlo methods, have recently been proposed by the present authors for the integration of functions belonging to certain "weighted" Sobolev spaces. The shifts in these rules were generated in a deterministic manner. In contrast, in this paper we generate these shifts randomly. This allows probabilistic estimates for the error in a given integral. It also reduces the number of operations required to find the generating vectors for the underlying lattice rules component-by-component. The rules thus constructed achieve a worst-case strong tractability error bound in an average or probabilistic sense.
We develop and justify an algorithm for the construction of quasi–Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found “component-by-component”: the ( d + 1 d+1 )-th component of the generator vector and the shift are obtained by successive 1 1 -dimensional searches, with the previous d d components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for n n -point rules with n n prime and all dimensions 1 to d d requires a total cost of O ( n 3 d 2 ) O(n^3d^2) operations. This may be reduced to O ( n 3 d ) O(n^3d) operations at the expense of O ( n 2 ) O(n^2) storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and n n up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.
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.
This short article studies a deterministic quasi-Monte Carlo lattice rule in weighted unanchored Sobolev spaces of smoothness 1 . Building on the error analysis by Kazashi and Sloan, we prove the existence of unshifted rank-1 lattice rules that achieve a worst-case error of O ( n − 1 / 4 ( log n ) 1 / 2 ) , with the implied constant independent of the dimension, under certain summability conditions on the weights. Although this convergence rate is inferior to the one achievable for the shifted-averaged root mean squared worst-case error, the result does not rely on random shifting or transformation and holds unconditionally without any conjecture, in contrast to the result of Kazashi and Sloan.
Polynomial lattice point sets are polynomial versions of classical lattice point sets and among the most widely used classes of node sets for quasi- Monte Carlo integration. In this paper, we study the worst-case integration error of digitally shifted polynomial lattice point sets and give step by step construction algorithms to obtain polynomial lattices that achieve a low worst-case error in certain weighted Sobolev spaces. The construction algorithm is a so-called com- ponent by component algorithm, choosing one component of the relevant point set at a time. Furthermore, under certain conditions on the weights, we achieve that there is only a polynomial or even no dependence of the worst-case error on the dimension of the integration problem.
In this paper, we study quasi-Monte Carlo (QMC) integration in weighted Sobolev spaces. In contrast to many previous results the QMC algorithms considered here are of open type, i.e., they are extensible in the number of sample points without having to discard the samples already used. As the underlying integration nodes we consider randomized Halton sequences in prime bases p=(p1,...,ps)\boldsymbol{p}=(p_1,...,p_s)p=(p1​,...,ps​) for which we study the root mean square (RMS) worst-case error. The randomization method is a p\boldsymbol{p}p-adic shift which is based on p\boldsymbol{p}p-adic arithmetic. The obtained error bounds are optimal in the order of magnitude of the number of sample nodes. Furthermore we obtain conditions on the coordinate weights under which the error bounds are independent of the dimension sss. In terms of the field of Information-Based Complexity this means that the corresponding QMC rule achieves a strong polynomial tractability error bound. Our findings on the RMS worst-case error of randomized Halton sequences can be carried over to the RMS L2L_2L2​-discrepancy. Except for the p\boldsymbol{p}p-adic shift our results are fully constructive and no search algorithms (such as the component-by-component algorithm) are required.
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.