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:2405.15799 · Winter Simulation Conference

An Improved Halton Sequence for Implementation in Quasi-Monte Carlo Methods

Nathan Kirk, Christiane Lemieux

Published Dec 15, 2024• 4 citations
arXivHTMLPDF

Abstract

Despite possessing the low-discrepancy property, the classical d-dimensional Halton sequence is known to exhibit poorly distributed projections when$d$becomes even moderately large. This, in turn, often implies bad performance when implemented in quasi-Monte Carlo (QMC) methods in comparison to, for example, the Sobol’ sequence. As an attempt to eradicate this issue, we propose an adapted Halton sequence built by integer and irrational based van der Corput sequences and show empirically improved performance with respect to the accuracy of estimates in numerical integration and simulation. In addition, for the first time, a scrambling algorithm is proposed for irrational based digital sequences.

DOI
10.1109/wsc63780.2024.10838773

Related papers

Computational investigations of low-discrepancy sequences

Ladislav Kocis, William J. Whiten

The Halton, Sobol, and Faure sequences and the Braaten-Weller construction of the generalized Halton sequence are studied in order to assess their applicability for the quasi Monte Carlo integration with large number of variates. A modification of the Halton sequence (the Halton sequence leaped) and a new construction of the generalized Halton sequence are suggested for unrestricted number of dimensions and are shown to improve considerably on the original Halton sequence. Problems associated with estimation of the error in quasi Monte Carlo integration and with the selection of test functions are identified. Then an estimate of the maximum error of the quasi Monte Carlo integration of nine test functions is computed for up to 400 dimensions and is used to evaluate the known generators mentioned above and the two new generators. An empirical formula for the error of the quasi Monte Carlo integration is suggested.

ACM Transactions on Mathematical Software•Jun 1, 1997•404 citations

Low discrepancy constructions in the triangle

Kinjal Basu, Art B. Owen

Most quasi-Monte Carlo research focuses on sampling from the unit cube. Many problems, especially in computer graphics, are defined via quadrature over the unit triangle. Quasi-Monte Carlo methods for the triangle have been developed by Pillands and Cools (2005) and by Brandolini et al. (2013). This paper presents two QMC constructions in the triangle with a vanishing discrepancy. The first is a version of the van der Corput sequence customized to the unit triangle. It is an extensible digital construction that attains a discrepancy below 12/sqrt(N). The second construction rotates an integer lattice through an angle whose tangent is a quadratic irrational number. It attains a discrepancy of O(log(N)/N) which is the best possible rate. Previous work strongly indicated that such a discrepancy was possible, but no constructions were available. Scrambling the digits of the first construction improves its accuracy for integration of smooth functions. Both constructions also yield convergent estimates for integrands that are Riemann integrable on the triangle without requiring bounded variation.

arXiv:1403.2649•Mar 11, 2014•5 citations

Quasi-Monte Carlo integration over non-cubical domains

Nilofar Mortazavi

Monte Carlo (MQ) method is a powerful tool to approximate high dimensional integrals. The disadvantage of ordinary MQ is the slow convergence rate by cause of the essential randomness of this method. Computations of this convergence can lead to pure time consuming. Quasi-Monte Carlo (QMC) method yields considerably better results since this method is a deterministic alternative which uses Low-Discrepancy sequences instead of random samples . There are a multiplicity of big open problems in QMC-methods, problems partly arising from applications and partly arising from theory. QMC are developed to integrate over unite cube, where it has much more accuracy than MC for integrands of bounded variation. Integration over more general spaces such as triangles, disks and Cartesian products of such spaces is more challenging for QMC. Nevertheless in real-world applications various problems are defined over such spaces. The aim of this thesis is to provide a survey of a solution of such problems of numerical integration defined over non-cubical spaces. We present QMC and randomised QMC (RQMC) constructions in the triangle with a vanishing discrepancy based on the recent work of Basu 2016. The QMC construction is a version of the Van der Corput-Halton sequences specially made to the unit triangle. The attraction of scrambled net is replication based error estimation for QMC with slightly the same accuracy as QMC, and for smooth enough integrands.

•Jan 1, 2017•0 citations

Scrambled quasirandom sequences and their applications

Hongmei Chi, Michael Mascagni

Quasi-Monte Carlo methods are a variant of ordinary Monte Carlo methods that employ highly uniform quasirandom numbers in place of Monte Carlo's pseudorandom numbers. Monte Carlo methods offer statistical error estimates; however, while quasi-Monte Carlo has a faster convergence rate than normal Monte Carlo, one cannot obtain error estimates from quasi-Monte Carlo sample values by any practical way. A recently proposed method, called randomized quasi-Monte Carlo methods, takes advantage of Monte Carlo and quasi-Monte Carlo methods. Randomness can be brought to bear on quasirandom sequences through scrambling and other related randomization techniques in randomized quasi-Monte Carlo methods, which provide an elegant approach to obtain error estimates for quasi-Monte Carlo based on treating each scrambled sequence as a different and independent random sample. The core of randomized quasi-Monte Carlo is to find an effective and fast algorithm to scramble (randomize) quasirandom sequences. This dissertation surveys research on algorithms and implementations of scrambled quasirandom sequences and proposes some new algorithms to improve the quality of scrambled quasirandom sequences. Besides obtaining error estimates for quasi-Monte Carlo, scrambling techniques provide a natural way to parallelize quasirandom sequences. This scheme is especially suitable for distributed or grid computing. By scrambling a quasirandom sequence we can produce a family of related quasirandom sequences. Finding one or a subset of optimal quasirandom sequences within this family is an interesting problem, as such optimal quasirandom sequences can be quite useful for quasi-Monte Carlo. The process of finding such optimal quasirandom sequences is called the derandomization of a randomized (scrambled) family. We summarize aspects of this technique and propose some new algorithms for finding optimal sequences from the Halton, Faure and Sobol sequences. Finally we explore applications of derandomization.

•Jan 1, 2004•8 citations

Deterministic algorithm for optimising the direction numbers of the Sobol’ sequence

Emanouil I. Atanassov

The quasi-Monte Carlo (QMC) methods use deterministic, usually low-discrepancy sequences, to improve the order of convergence when compared with Monte Carlo methods dealing with the same problem. Although this improved convergence depends on the smoothness properties of the functions under consideration and sometimes cannot be established theoretically, good practical results were obtained in many areas, notably in Financial Mathematics. Most of the QMC methods do not depend on particular properties of the sequences used beyond their good distribution in a suitable multidimensional space. Many families of low-discrepancy sequences have been studies, with the family of the Sobol sequences being not only one of the oldest but also the most popular in practical applications. Since these sequences have many free parameters, it is desirable to have methods to obtain a good set of parameters, suitable for a wide class of problems. In this work we propose a fully deterministic method for optimisation of the direction numbers of the Sobol sequences that is flexible in taking into account smoothness properties of the potential sub-integral functions. We demonstrate how by implementing this algorithm on modern GPUs it is possible to obtain good sets of direction numbers within a reasonable timeframe. The numerical tests demonstrate the significant advantage in terms of accuracy that is observed, which makes the corresponding QMC methods even more competitive.

Mathematics and Education in Mathematics•Jan 1, 2021•0 citations

QMC integration errors and quasi-asymptotics

Ilya M. Sobol, Boris V. Shukhman

Abstract A crude Monte Carlo (MC) method allows to calculate integrals over a d-dimensional cube. As the number N of integration nodes becomes large, the rate of probable error of the MC method decreases as O ⁢ ( 1 / N ) {O(1/\sqrt{N})} . The use of quasi-random points instead of random points in the MC algorithm converts it to the quasi-Monte Carlo (QMC) method. The asymptotic error estimate of QMC integration of d-dimensional functions contains a multiplier 1 / N {1/N} . However, the multiplier ( ln ⁡ N ) d {(\ln N)^{d}} is also a part of the error estimate, which makes it virtually useless. We have proved that, in the general case, the QMC error estimate is not limited to the factor 1 / N {1/N} . However, our numerical experiments show that using quasi-random points of Sobol sequences with N = 2 m {N=2^{m}} with natural m makes the integration error approximately proportional to 1 / N {1/N} . In our numerical experiments, d ≤ 15 {d\leq 15} , and we used N ≤ 2 40 {N\leq 2^{40}} points generated by the SOBOLSEQ16384 code published in 2011. In this code, d ≤ 2 14 {d\leq 2^{14}} and N ≤ 2 63 {N\leq 2^{63}} .

Monte Carlo Methods and Applications•Jul 16, 2020•2 citations
Despite possessing the low-discrepancy property, the classical d-dimensional Halton sequence is known to exhibit poorly distributed projections whendddbecomes even moderately large. This, in turn, often implies bad performance when implemented in quasi-Monte Carlo (QMC) methods in comparison to, for example, the Sobol’ sequence. As an attempt to eradicate this issue, we propose an adapted Halton sequence built by integer and irrational based van der Corput sequences and show empirically improved performance with respect to the accuracy of estimates in numerical integration and simulation. In addition, for the first time, a scrambling algorithm is proposed for irrational based digital sequences.
The Halton, Sobol, and Faure sequences and the Braaten-Weller construction of the generalized Halton sequence are studied in order to assess their applicability for the quasi Monte Carlo integration with large number of variates. A modification of the Halton sequence (the Halton sequence leaped) and a new construction of the generalized Halton sequence are suggested for unrestricted number of dimensions and are shown to improve considerably on the original Halton sequence. Problems associated with estimation of the error in quasi Monte Carlo integration and with the selection of test functions are identified. Then an estimate of the maximum error of the quasi Monte Carlo integration of nine test functions is computed for up to 400 dimensions and is used to evaluate the known generators mentioned above and the two new generators. An empirical formula for the error of the quasi Monte Carlo integration is suggested.
Most quasi-Monte Carlo research focuses on sampling from the unit cube. Many problems, especially in computer graphics, are defined via quadrature over the unit triangle. Quasi-Monte Carlo methods for the triangle have been developed by Pillands and Cools (2005) and by Brandolini et al. (2013). This paper presents two QMC constructions in the triangle with a vanishing discrepancy. The first is a version of the van der Corput sequence customized to the unit triangle. It is an extensible digital construction that attains a discrepancy below 12/sqrt(N). The second construction rotates an integer lattice through an angle whose tangent is a quadratic irrational number. It attains a discrepancy of O(log(N)/N) which is the best possible rate. Previous work strongly indicated that such a discrepancy was possible, but no constructions were available. Scrambling the digits of the first construction improves its accuracy for integration of smooth functions. Both constructions also yield convergent estimates for integrands that are Riemann integrable on the triangle without requiring bounded variation.
Monte Carlo (MQ) method is a powerful tool to approximate high dimensional integrals. The disadvantage of ordinary MQ is the slow convergence rate by cause of the essential randomness of this method. Computations of this convergence can lead to pure time consuming. Quasi-Monte Carlo (QMC) method yields considerably better results since this method is a deterministic alternative which uses Low-Discrepancy sequences instead of random samples . There are a multiplicity of big open problems in QMC-methods, problems partly arising from applications and partly arising from theory. QMC are developed to integrate over unite cube, where it has much more accuracy than MC for integrands of bounded variation. Integration over more general spaces such as triangles, disks and Cartesian products of such spaces is more challenging for QMC. Nevertheless in real-world applications various problems are defined over such spaces. The aim of this thesis is to provide a survey of a solution of such problems of numerical integration defined over non-cubical spaces. We present QMC and randomised QMC (RQMC) constructions in the triangle with a vanishing discrepancy based on the recent work of Basu 2016. The QMC construction is a version of the Van der Corput-Halton sequences specially made to the unit triangle. The attraction of scrambled net is replication based error estimation for QMC with slightly the same accuracy as QMC, and for smooth enough integrands.
Quasi-Monte Carlo methods are a variant of ordinary Monte Carlo methods that employ highly uniform quasirandom numbers in place of Monte Carlo's pseudorandom numbers. Monte Carlo methods offer statistical error estimates; however, while quasi-Monte Carlo has a faster convergence rate than normal Monte Carlo, one cannot obtain error estimates from quasi-Monte Carlo sample values by any practical way. A recently proposed method, called randomized quasi-Monte Carlo methods, takes advantage of Monte Carlo and quasi-Monte Carlo methods. Randomness can be brought to bear on quasirandom sequences through scrambling and other related randomization techniques in randomized quasi-Monte Carlo methods, which provide an elegant approach to obtain error estimates for quasi-Monte Carlo based on treating each scrambled sequence as a different and independent random sample. The core of randomized quasi-Monte Carlo is to find an effective and fast algorithm to scramble (randomize) quasirandom sequences. This dissertation surveys research on algorithms and implementations of scrambled quasirandom sequences and proposes some new algorithms to improve the quality of scrambled quasirandom sequences. Besides obtaining error estimates for quasi-Monte Carlo, scrambling techniques provide a natural way to parallelize quasirandom sequences. This scheme is especially suitable for distributed or grid computing. By scrambling a quasirandom sequence we can produce a family of related quasirandom sequences. Finding one or a subset of optimal quasirandom sequences within this family is an interesting problem, as such optimal quasirandom sequences can be quite useful for quasi-Monte Carlo. The process of finding such optimal quasirandom sequences is called the derandomization of a randomized (scrambled) family. We summarize aspects of this technique and propose some new algorithms for finding optimal sequences from the Halton, Faure and Sobol sequences. Finally we explore applications of derandomization.
The quasi-Monte Carlo (QMC) methods use deterministic, usually low-discrepancy sequences, to improve the order of convergence when compared with Monte Carlo methods dealing with the same problem. Although this improved convergence depends on the smoothness properties of the functions under consideration and sometimes cannot be established theoretically, good practical results were obtained in many areas, notably in Financial Mathematics. Most of the QMC methods do not depend on particular properties of the sequences used beyond their good distribution in a suitable multidimensional space. Many families of low-discrepancy sequences have been studies, with the family of the Sobol sequences being not only one of the oldest but also the most popular in practical applications. Since these sequences have many free parameters, it is desirable to have methods to obtain a good set of parameters, suitable for a wide class of problems. In this work we propose a fully deterministic method for optimisation of the direction numbers of the Sobol sequences that is flexible in taking into account smoothness properties of the potential sub-integral functions. We demonstrate how by implementing this algorithm on modern GPUs it is possible to obtain good sets of direction numbers within a reasonable timeframe. The numerical tests demonstrate the significant advantage in terms of accuracy that is observed, which makes the corresponding QMC methods even more competitive.
Abstract A crude Monte Carlo (MC) method allows to calculate integrals over a d-dimensional cube. As the number N of integration nodes becomes large, the rate of probable error of the MC method decreases as O ⁢ ( 1 / N ) {O(1/\sqrt{N})} . The use of quasi-random points instead of random points in the MC algorithm converts it to the quasi-Monte Carlo (QMC) method. The asymptotic error estimate of QMC integration of d-dimensional functions contains a multiplier 1 / N {1/N} . However, the multiplier ( ln ⁡ N ) d {(\ln N)^{d}} is also a part of the error estimate, which makes it virtually useless. We have proved that, in the general case, the QMC error estimate is not limited to the factor 1 / N {1/N} . However, our numerical experiments show that using quasi-random points of Sobol sequences with N = 2 m {N=2^{m}} with natural m makes the integration error approximately proportional to 1 / N {1/N} . In our numerical experiments, d ≤ 15 {d\leq 15} , and we used N ≤ 2 40 {N\leq 2^{40}} points generated by the SOBOLSEQ16384 code published in 2011. In this code, d ≤ 2 14 {d\leq 2^{14}} and N ≤ 2 63 {N\leq 2^{63}} .