umontreal.iro.lecuyer.hups
Class SobolSequence

java.lang.Object
  umontreal.iro.lecuyer.hups.PointSet
      umontreal.iro.lecuyer.hups.DigitalNet
          umontreal.iro.lecuyer.hups.DigitalNetBase2
              umontreal.iro.lecuyer.hups.DigitalSequenceBase2
                  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 = 2^k points of a Sobol' sequence. Values of n up to 2³⁰ are allowed.

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

v_{j, c} = m_{j, c}2^-c = ∑_l=1^cv_{j, c, l}2^-l,

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

m_{j, c} = ∑_l=1^cv_{j, c, l}2^c-l,

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

For each dimension j, the integers m_{j, c} are defined by selecting a primitive polynomial over F₂ of degree c_j,

f_j(z) = z^c_j + a_{j, 1}z^c_j-1 + ^... + a_{j, cj},

and the first c_j integers m_{j, 0},..., m_{j, cj-1}. Then the following integers m_{j, cj}, m_{j, cj+1},... are determined by the recurrence

m_{j, c} = 2a_{j, 1}m_{j, c-1}⊕ ^... ⊕2^c_j-1a_{j, cj-1}m_{j, c-cj+1}⊕2^c_jm_{j, c-cj}⊕m_{j, c-cj}

for c >= c_j, or equivalently,

v_{j, c, l} = a_{j, 1}v_{j, c-1, l}⊕ ^... ⊕a_{j, cj-1}v_{j, c-cj+1, l}⊕v_{j, c-cj, l}⊕v_{j, 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 f_j(z) are all distinct, one obtains a (t, s)-sequence whose t-value does not exceed c₀ + ^... + c_s-1 + 1 - s. He then suggested to list the set of all primitive polynomials over F₂ by increasing order of degree, starting with f₀(z)≡1 (whose corresponding matrix C₀ is the identity), and take f_j(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 f_j(z) is stored in the form of the integer 2^c_j + a_{j, 1}2^c_j-1 + ^... + a_{j, 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 = 2^k 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 = 2^k points and w output digits, in dimension dim, formed by taking the first n points of the Sobol' sequence. The predefined generator matrices C_j 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(log₂n).

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 = 2^k 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 m_i are the direction numbers. Thus if a = (a₁a₂…a_s-1)₂ for a given s, then the polynomial is x^s + a₁x^s-1 + a₂x^s-2 + ^... + a_s-1x + 1. For example, if s = 4 and a = 4 = 100₂, then the polynomial is x⁴ + x³ + 1.

Parameters:

k - number of points is 2^k

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 = 2^k from now on.

Specified by:

extendSequence in class DigitalSequenceBase2

Parameters:

k - there will be 2^k points