SSJ
V. 2.6.

umontreal.iro.lecuyer.hups
Class SobolSequence

java.lang.Object
  extended by umontreal.iro.lecuyer.hups.PointSet
      extended by umontreal.iro.lecuyer.hups.DigitalNet
          extended by umontreal.iro.lecuyer.hups.DigitalNetBase2
              extended by umontreal.iro.lecuyer.hups.DigitalSequenceBase2
                  extended by umontreal.iro.lecuyer.hups.SobolSequence

public class SobolSequence
extends DigitalSequenceBase2

This class implements digital nets or digital sequences in base 2 formed by the first n = 2k points of a Sobol' sequence. Values of n up to 230 are allowed.

In Sobol's proposal, the generator matrices Cj are upper triangular matrices defined by a set of direction numbers

vj, c = mj, c2-c = ∑l=1cvj, c, l2-l,

where each mj, c is an odd integer smaller than 2c, for c = 1,..., k and j = 0,..., s - 1. The digit vj, c, l is the element (l, c) of Cj, so vj, c represents column c of Cj. One can also write

mj, c = ∑l=1cvj, c, l2c-l,

so column c of Cj contains the c digits of the binary expansion of mj, c, from the most to the least significant, followed by w - c zeros, where w is the number of output digits. Since each mj, c is odd, the first k rows of each Cj form a non-singular upper triangular matrix whose diagonal elements are all ones.

For each dimension j, the integers mj, c are defined by selecting a primitive polynomial over F2 of degree cj,

fj(z) = zcj + aj, 1zcj-1 + ... + aj, cj,

and the first cj integers mj, 0,..., mj, cj-1. Then the following integers mj, cj, mj, cj+1,... are determined by the recurrence

mj, c = 2aj, 1mj, c-1 ... ⊕2cj-1aj, cj-1mj, c-cj+1⊕2cjmj, c-cjmj, c-cj

for c >= cj, or equivalently,

vj, c, l = aj, 1vj, c-1, l ... aj, cj-1vj, c-cj+1, lvj, c-cj, lvj, c-cj, l+cj

for l >=  0, where means bitwise exclusive or (i.e., bitwise addition modulo 2). Sobol' has shown that with this construction, if the primitive polynomials fj(z) are all distinct, one obtains a (t, s)-sequence whose t-value does not exceed c0 + ... + cs-1 + 1 - s. He then suggested to list the set of all primitive polynomials over F2 by increasing order of degree, starting with f0(z)≡1 (whose corresponding matrix C0 is the identity), and take fj(z) as the (j + 1)th polynomial in the list, for j >=  0.

This list of primitive polynomials, as well as default choices for the direction numbers, are stored in precomputed tables. The ordered list of primitive polynomials was taken from Florent Chabaud's web site, at http://fchabaud.free.fr/. Each polynomial fj(z) is stored in the form of the integer 2cj + aj, 12cj-1 + ... + aj, cj, whose binary representation gives the polynomial coefficients.

For the set of direction numbers, there are several possibilities based on different selection criteria. The original values proposed by Sobol' and implemented in the code of Bratley and Fox for j <= 40 were selected in terms of his properties A and A', which are equivalent to s-distribution with one and two bits of accuracy, respectively. The default direction numbers used here have been taken from Lemieux et al. For j <= 40, they are the same as in Bratley and Fox. Several files of parameters for Sobol sequences are given on F. Kuo's Web site at http://web.maths.unsw.edu.au/~fkuo/sobol/index.html.


Constructor Summary
SobolSequence(int n, int dim)
          Constructs a Sobol point set with at least n points and 31 output digits, in dimension dim.
SobolSequence(int k, int w, int dim)
          Constructs a new digital net with n = 2k points and w output digits, in dimension dim, formed by taking the first n points of the Sobol' sequence.
SobolSequence(String filename, int k, int w, int dim)
          Constructs a new digital net using the direction numbers provided in file filename.
 
Method Summary
 void extendSequence(int k)
          Increases the number of points to n = 2k from now on.
 String toString()
          Formats a string that contains information about the point set.
 
Methods inherited from class umontreal.iro.lecuyer.hups.DigitalSequenceBase2
iteratorShift, iteratorShiftNoGray, toNet, toNetShiftCj
 
Methods inherited from class umontreal.iro.lecuyer.hups.DigitalNetBase2
addRandomShift, addRandomShift, clearRandomShift, getCoordinate, getCoordinateNoGray, iBinomialMatrixScramble, iBinomialMatrixScrambleFaurePermut, iBinomialMatrixScrambleFaurePermutAll, iBinomialMatrixScrambleFaurePermutDiag, iterator, iteratorNoGray, leftMatrixScramble, leftMatrixScrambleDiag, leftMatrixScrambleFaurePermut, leftMatrixScrambleFaurePermutAll, leftMatrixScrambleFaurePermutDiag, printGeneratorMatrices, printGeneratorMatricesTrans, rightMatrixScramble, stripedMatrixScramble, stripedMatrixScrambleFaurePermutAll
 
Methods inherited from class umontreal.iro.lecuyer.hups.DigitalNet
eraseOriginalGeneratorMatrices, resetGeneratorMatrices, unrandomize
 
Methods inherited from class umontreal.iro.lecuyer.hups.PointSet
addRandomShift, addRandomShift, formatPoints, formatPoints, formatPoints, formatPoints, formatPointsBase, formatPointsBase, formatPointsBase, formatPointsBase, formatPointsNumbered, formatPointsNumbered, getDimension, getNumPoints, getStream, randomize, randomize, randomize, randomize, randomize, setStream
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

SobolSequence

public SobolSequence(int k,
                     int w,
                     int dim)
Constructs a new digital net with n = 2k points and w output digits, in dimension dim, formed by taking the first n points of the Sobol' sequence. The predefined generator matrices Cj are w×k. Restrictions: 0 <= k <= 30, k <= w and dim  <= 360.

Parameters:
k - there will be 2^k points
w - number of output digits
dim - dimension of the point set

SobolSequence

public SobolSequence(int n,
                     int dim)
Constructs a Sobol point set with at least n points and 31 output digits, in dimension dim. Equivalent to SobolSequence (k, 31, dim) with k = ceil(log2n).

Parameters:
dim - dimension of the point set
n - minimal number of points

SobolSequence

public SobolSequence(String filename,
                     int k,
                     int w,
                     int dim)
Constructs a new digital net using the direction numbers provided in file filename. The net has n = 2k points, w output digits and dimension dim. The file can be either on the user's host, or somewhere on the Internet: in that case, the full url address must be given using either the http or ftp protocol. For example:

net = new SobolSequence(
"http://web.maths.unsw.edu.au/˜fkuo/sobol/joe-kuo-6.16900", k, w, dim);

The file must have the following format (the first line is treated as a comment by the program and discarded):

dim s a mi
2 1 0 1
3 2 1 1 3
4 3 1 1 3 1
5 3 2 1 1 1
6 4 1 1 1 3 3
7 4 4 1 3 5 13
   
dim is the dimension, s the degree of the polynomial, the binary representation of a gives the inner coefficients of the polynomial (the first and the last coefficients are always 1), and mi are the direction numbers. Thus if a = (a1a2as-1)2 for a given s, then the polynomial is xs + a1xs-1 + a2xs-2 + ... + as-1x + 1. For example, if s = 4 and a = 4 = 1002, then the polynomial is x4 + x3 + 1.

Parameters:
k - number of points is 2k
w - number of output digits
dim - dimension of the point set
filename - file containing the direction numbers
Method Detail

toString

public String toString()
Description copied from class: PointSet
Formats a string that contains information about the point set.

Overrides:
toString in class DigitalNetBase2
Returns:
string representation of the point set information

extendSequence

public void extendSequence(int k)
Description copied from class: DigitalSequenceBase2
Increases the number of points to n = 2k from now on.

Specified by:
extendSequence in class DigitalSequenceBase2
Parameters:
k - there will be 2^k points

SSJ
V. 2.6.

To submit a bug or ask questions, send an e-mail to Pierre L'Ecuyer.