V. 1.2.5.

Class SobolSequence

  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 231 are allowed, in a maximum of 360 dimensions.

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

Constructor Summary
SobolSequence(int n, int dim)
          Constructs a Sobol point set with at least n points in dim dimensions.
SobolSequence(int k, int w, int dim)
          Constructs a new digital net with n = 2k points and w = 31 output digits, in dim dimensions, formed by taking the first n points of the Sobol' sequence.
Method Summary
 void extendSequence(int k)
          Increases the number of points to n = 2k from now on.
 String toString()
          Formats a string that contains the 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, leftMatrixScrambleRest, resetGeneratorMatrices, unrandomize
Methods inherited from class umontreal.iro.lecuyer.hups.PointSet
addRandomShift, addRandomShift, formatPoints, formatPoints, getDimension, getNumPoints, randomize, randomize, randomize, randomize
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail


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

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


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

dim - dimension of the point set
n - minimal number of points
Method Detail


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

toString in class DigitalNetBase2
string representation of the point set information


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
k - there will be 2^k points

V. 1.2.5.

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