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:
 S. Joe and F. Y. Kuo, Remark on Algorithm 659: Implementing Sobol's
quasirandom sequence generator, ACM Trans. Math. Softw. 29, 4957 (2003).
Link to paper.
 S. Joe and F. Y. Kuo, Constructing Sobol sequences with better
twodimensional projections, SIAM J. Sci. Comput. 30, 26352654 (2008).
Link to paper.
Here is a 3page 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.
 The file newjoekuo6.21201
contains the direction numbers obtained using the
search criterion D^{(6)} up to dimension 21201.
This is our recommended choice.
 The file newjoekuo7.21201
contains the direction numbers obtained using the
search criterion D^{(7)} up to dimension 21201.
 The file newjoekuo5.21201
contains the direction numbers obtained using the
search criterion D^{(5)} up to dimension 21201.
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 tvalue first occurs 


tvalue 

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 BSDstyle 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 newjoekuo6.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.