Sobol sequence generator

This page contains the primitive polynomials and various sets of initial direction numbers for generating Sobol sequences.

This is a joint project between Stephen Joe and Frances Kuo. More details can be found in the following papers:

  1. S. Joe and F. Y. Kuo, Remark on Algorithm 659: Implementing Sobol's quasirandom sequence generator, ACM Trans. Math. Softw. 29, 49-57 (2003). Link to paper.
  2. S. Joe and F. Y. Kuo, Constructing Sobol sequences with better two-dimensional projections, SIAM J. Sci. Comput. 30, 2635-2654 (2008). Link to paper.
Here is a 3-page notes on generating Sobol sequences.

New sets of direction numbers from [2]

The following files contain primitive polynomials and direction numbers obtained using the search algorithm in [2]. The columns in the files are d, s, a, m, where d is the dimension, s is the degree of the primitive polynomial, a is the number representing the coefficients, and m is the list of initial direction numbers. We arrange the primitive polynomials in increasing order of their degrees, and for those with the same degree we systematically arrange them in increasing order of the numbers a. Property A is satisfied up to dimension 1111. Our target dimension is 21201. These files will be updated regularly as new data become available. They were last updated on 21 October 2009.

Other sets of direction numbers

The following files contain primitive polynomials and direction numbers obtained based on some earlier version of the search algorithm from [2]. The error criteria are similar but slightly different to those in [2]. The columns in the files are d, s, a, m as above. For the first 40 dimensions, we use the primitive polynomials from the Bratley and Fox (1988) paper. From dimension 41 onward, we arrange the primitive polynomials in increasing order of their degrees, and for those with the same degree we systematically arrange them in increasing order of the numbers a. As a result, the polynomials from the first 46 dimensions are in a different order to the new data from [2] above. Property A is satisfied in all dimensions. These files will not be updated further.

Simple C++ program

The file sobol.cc is a simple C++ program for generating Sobol points in graycode order. This program and the accompanying direction numbers above are covered by this BSD-style licence.
Compile the program with the command
g++ -o sobol sobol.cc
Then run the program with three arguments N D FILENAME. For example, the command
./sobol 10 3 joe-kuo-6.19900
gives the output
0 0 0
0.5 0.5 0.5
0.75 0.25 0.25
0.25 0.75 0.75
0.375 0.375 0.625
0.875 0.875 0.125
0.625 0.125 0.875
0.125 0.625 0.375
0.1875 0.3125 0.9375
0.6875 0.8125 0.4375
These are the first 10 Sobol points in 3 dimensions.
WARNING: This simple program generates ALL the points at once and stores everything in memory. It is NOT meant to be used directly for practical computations where the total number of points is large and/or the dimension is high. For such computations the points should be generated ONE POINT AT A TIME and cleared from memory immediately after the associated function evaluation is finished. It should be straight forward to extract the appropriate c++ code for doing this from our simple program.

Questions or comments?

We are very keen to hear from you regarding your experience with these direction numbers. Please email Frances Kuo <f.kuo@unsw.edu.au> and Stephen Joe <stephenj@math.waikato.ac.nz>.

If you have any publication arising which makes use of the material here, it would be appreciated if you could cite our ACM Trans. Math. Softw. paper and/or our SIAM J. Sci. Comput. paper as appropriate.