An overview of the Low Discrepancy toolbox.
The goal of this toolbox is to provide a collection of low discrepancy sequences. These sequences try to produce numbers which favor the convergence of a Monte-Carlo simulation by reducing the discrepancy. These random numbers are designed to be used in a Monte-Carlo simulation. For example, low discrepancy sequences provide a higher convergence rate to the Monte-Carlo method when used in numerical integration. The toolbox takes into account the dimension of the problem, i.e. generate vectors with arbitrary size.
Low Discrepancy sequences are designed to be able to produce real values uniform in the [0,1[^s interval, where s is the dimension of the space.
See the provided demonstrations for sample examples of this library.
The list of sequences which are provided in this component is the following.
The Halton sequence.
The leaped Halton sequence.
The scrambled Halton sequence of Kocis and Whiten ("Reverse Radix" or "RR2").
The Reverse Halton sequence of Vandewoestyne and Cools.
The Faure sequence.
The Sobol sequence.
The scrambled Sobol sequence : Owen, Faure-Tezuka or Owen-Faure-Tezuka scramblings.
The Niederreiter base 2 and arbitrary base sequence.
The current component has the following features :
manage arbitrary number of dimensions,
skips a given number of elements in the sequence,
leaps (i.e. ignores) a given number of elements from call to call,
fast sequences based on compiled source code,
suggest optimal settings to make the best use of the sequences,
object oriented programming, if necessary.
get directly the dimension-th coordinate, without generating the coordinates 1,2,...,dimension-1. This is a convenient feature for discrete event simulation (piecewise deterministic Markov processes), where the number of jumps is not known in advance for all chains.
The following example generates 20 points from a Sobol sequence in dimension 4. This is a simplified use of the library, where we know in advance the number of experiments to perform.
Assume now that we want to use a scrambled Halton sequence. The following calling sequence creates a scrambled Halton sequence with 20 points in 4 dimensions. This may potentially reduce the correlations which may appear in high dimensions.
It may happen that we have to generate the points block-by-block, instead of all-at-once. In this case, we may use the following functions. The following example creates 1000 points in dimension 4 from the Sobol sequence. This way of using the library allows to get a complete control over the parameters of the sequence. It also allows to generate the points one by one, which may be useful to save memory.
The function lowdisc_methods returns the list of available sequences. The following script displays the available sequences and a table displaying the speed, maximum dimension and maximum number of calls for all sequences.
// Get all the available sequences. seqmat = lowdisc_methods (); // Get the speed, maximum dimension and // maximum number of calls for all sequences seqmat = lowdisc_methods (); mprintf("%-20s %-10s %-10s\n", "Name" , .. "Max Dim" , "Max Call" ); for seqname = seqmat' lds = lowdisc_new(seqname); dimmax = lowdisc_get(lds,"-dimmax"); nbsimmax = lowdisc_get(lds,"-nbsimmax"); mprintf("%-20s %-10d %-10d\n", seqname , .. dimmax , nbsimmax ); lds = lowdisc_destroy(lds); end | ![]() | ![]() |
The previous script produces the following output. When the maximum number of calls is equal to -1, this means that there is, in principle, no limit in the number of elements which can be generated.
Name Max Dim Max Call halton 100 2147483647 faure 541 2147483647 sobol 1111 1073741823 niederreiter 50 2147483647
The main components in this toolbox are the following.
The lowdisc_ldgen
function
can produce a complete set of points, given the name of a sequence and
the number of dimension.
Moreover, this function makes use of optimized skip
and leap
parameters,
which may reduce the discrepancy of the sequence.
Moreover, the number of generated points can be optimized to reduce
the discrepancy.
This is the flagship of this toolbox.
Sequences:
The lowdisc_*
functions provide the highest level object oriented
functions.
They allow to access to any sequence with a constructor based
on a string representing the sequence. For example,
lds = lowdisc_new("halton")
creates a new Halton sequence.
In this framework, the lowdisc component allows to access to all sequences
with a single API, where all the methods are valid for all sequences and
all sequences share the same options.
Static Functions:
These functions are macros which provides parameters which can
be used in low discrepancy sequences such as skip
and leap
parameters, or tables of prime numbers.
The zero vector is never produced by the low discrepancy generators in this toolbox. This allows to avoid problem when inverting a cumulated distribution function, because the zero probability may be associated with an infinite outcome (e.g. for the multivariate normale distribution).
However, in order to graphically show the low discrepancy properties
of some sequences, it may be useful to include the zero.
For example, the following code compute the first 100 points of the
Halton sequence in s=5 dimensions.
Then we use the zeros
function in order
to insert the zero row vector at the start of the sequence.
s=5; u=lowdisc_ldgen(10,s, "halton" ); u = [zeros(1,s);u] | ![]() | ![]() |
Michael Baudin thanks John Burkardt for his help during the development of this library.
Thanks to Alan Cornet, Pierre Marechal for the technical help for this project.
Thanks to Jean-Philippe Chancelier for finding bugs in the source code of the gateway.
This toolbox is distributed under the GNU LGPL license.
"Monte-Carlo methods in Financial Engineering", Paul Glasserman, Springer, 2003
"Algorithm 247: Radical-inverse quasi-random point sequence", J. H. Halton, 1964. Commun. ACM 7, 12 (Dec. 1964), 701-702
"Good permutations for deterministic scrambled Halton sequences in terms of L2-discrepancy", B. Vandewoestyne and R. Cools, Computational and Applied Mathematics 189, 2006
"Low-discrepancy and low-dispersion sequences", Harald Niederreiter, Journal of Number Theory, Volume 30, 1988, pages 51-70.
"Algorithm 647: Implementation and Relative Efficiency of Quasirandom Sequence Generators", B. L. Fox, 1986. ACM Trans. Math. Softw. 12, 4 (Dec. 1986), 362-376.
"Algorithm 659: Implementing Sobol's quasirandom sequence generator.", P. Bratley and B. L. Fox, 1988. ACM Trans. Math. Softw. 14, 1 (Mar. 1988), 88-100.
"Remark on Algorithm 659: Implementing Sobol's Quasirandom Sequence Generator", Stephen Joe, Frances Kuo, ACM Transactions on Mathematical Software, Volume 29, Number 1, March 2003, pages 49-57.
"Implementation and Tests of Low Discrepancy Sequences", Paul Bratley, Bennett Fox, Harald Niederreiter, ACM Transactions on Modeling and Computer Simulation, Volume 2, Number 3, July 1992, pages 195-213.
"Algorithm 738: Programs to generate Niederreiter's low-discrepancy sequences", P. Bratley, B. L. Fox, and H. Niederreiter, 1994. ACM Trans. Math. Softw. 20, 4 (Dec. 1994), 494-495.
"Algorithm 823: Implementing scrambled digital sequences", H. S. Hong and F. J. Hickernell, 2003. ACM Trans. Math. Softw. 29, 2 (Jun. 2003), 95-109.
"Discrepancy of sequences associated with a number system (in dimension one)", Faure Henri, Bull. Soc. Math. France 109, no. 2, 143--182, 1981
"Numerical Recipes in Fortran: The Art of Scientific Computing", William Press, Brian Flannery, Saul Teukolsky, William Vetterling, Second Edition, Cambridge University Press, 1992
"Comparison of Point Sets and Sequences for Quasi-Monte Carlo and for Random Number Generation.", L'Ecuyer, P. 2008. In Proceedings of the 5th international Conference on Sequences and their Applications (Lexington, KY, USA, September 14 - 18, 2008). S. W. Golomb, M. G. Parker, A. Pott, and A. Winterhof, Eds. Lecture Notes In Computer Science, vol. 5203. Springer-Verlag, Berlin, Heidelberg, 1-17.
"Computational investigations of low-discrepancy sequences", Kocis, L. and Whiten, W. J. 1997. ACM Trans. Math. Softw. 23, 2 (Jun. 1997), 266-294.
"Gnu Scientific Library - The Reverse Halton Sequence", Olivier Teytaud, 2007
"USSR Computational Mathematics and Mathematical Physics", Ilya Sobol, Volume 16, pages 236-242, 1977.
"The Production of Points Uniformly Distributed in a Multidimensional Cube" (in Russian), Ilya Sobol, YL Levitan, Preprint IPM Akad. Nauk SSSR, Number 40, Moscow 1976.
"Random Number Generation and Quasi-Monte Carlo Methods", Harald Niederreiter, SIAM, 1992.