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. They were last updated on 16 September 2010. The dimension 21201 was our target dimension. At this stage we have no plan to update these further.

NOTE: The files posted here prior to June 2010 have been removed because we identified some undesirable properties which can affect the quality of the resulting Sobol sequence. The three replacement files do not have these undesirable properties.

WARNING: Our search criteria in [2] incorporated some "weights" so that the projections with earlier variables are treated as more important than those with later variables. This choice of weights makes sense when the variables are arranged in the order of decreasing importance. This choice of weights may not be suitable for the type of problems where the interactions between successive variables are the more important ones; in that case, a different choice of weights should be used in the search criteria, thus leading to a different set of direction numbers.

Other sets of direction numbers

The following files contain primitive polynomials and direction numbers obtained using an 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.

Comparison of [2] and [1]

The following table compares the direction numbers obtained using the search criterion D(6) with the direction numbers from [1]. This table is an updated version of [2,Table 3.8] correponding to the new replacement files.

Dimension at which each t-value first occurs
  t-value
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
m=10 D(6) 2 3 4 5 9 16 32 76 167 402 >21201               
[1] 2 3 4 5 8 15 21 23 18 36 >1111               
m=12 D(6) 2 3 4 6 10 16 34 40 109 233 559 1069 >21201           
[1] 2 3 4 7 10 10 10 22 35 51 96 61 >1111           
m=14 D(6) 2 3 4 6 8 12 22 48 85 164 383 720 1235 1861 >21201       
[1] 2 3 4 5 9 10 25 17 40 55 67 67 131 61 >1111       
m=16 D(6) 2 3 4 6 8 14 15 35 80 159 255 500 837 1553 2375 2721 >21201    
[1] 2 3 4 6 9 8 15 13 32 58 69 74 102 95 447 167 >1111    
m=18 D(6) 2 3 4 7 8 11 15 35 70 108 213 414 720 1177 1819 2616 3092 3677 >21201
[1] 2 3 4 7 7 10 12 21 28 25 103 126 115 114 196 232 665 380 >1111

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 new-joe-kuo-6.21201
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 straightforward to extract the appropriate C++ code for doing this from our simple program.

Questions or comments?

We are 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.