SSJ
V. labo.

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
Direct Known Subclasses:
LeftScrambledSobolSequence

public class SobolSequence
extends DigitalSequenceBase2

SobolSequence

This class implements digital nets or digital sequences in base 2 formed by the first n = 2k points of a Sobol' sequence[#!rSOB67a!#,#!rSOB76b!#]. 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 = $\displaystyle \htsum_{{l=1}}^{c}$vj, 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 = [tex2html_wrap_indisplay357]vj, 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 ccj, 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[#!rSOB67a!#] 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[#!rBRA88c!#] 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. We should eventually have other choices for the direction numbers.


Constructor Summary
SobolSequence(int n, int dim)
          .
SobolSequence(int k, int w, int dim)
          .
SobolSequence(String filename, int k, int w, int dim)
          .
 
Method Summary
 void extendSequence(int k)
          Increases the number of points to n = 2k from now on.
 String toString()
          .
 
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)
. \begin{tabb}
 Constructs a new digital net with $n = 2^k$\ points and $w$
 outp...
 ... Restrictions: $0\le k\le 30$, $k\le w$\ and \texttt{dim} $ \le 360$.
 \end{tabb}
kthere will be 2^k points wnumber of output digits dimdimension of the point set


SobolSequence

public SobolSequence(int n,
                     int dim)
. \begin{tabb}
 Constructs a Sobol point set with \emph{at least} \texttt{n} point...
 ...\texttt{SobolSequence (k, 31, dim)} with $k = \lceil \log_2 n\rceil$.
 \end{tabb}
dimdimension of the point set nminimal number of points


SobolSequence

public SobolSequence(String filename,
                     int k,
                     int w,
                     int dim)
. \begin{tabb}
 Constructs a new digital net using the direction numbers provided ...
 ... if $s=4$\ and $a=4 = 100_2$, then the
 polynomial is $x^4 + x^3 +1$.
 \end{tabb}
knumber of points is 2k wnumber of output digits dimdimension of the point set filenamefile containing the direction numbers

Method Detail

toString

public String toString()
Description copied from class: PointSet
. \begin{tabb}
 Formats a string that contains information about the point set.
 \end{tabb}
string representation of the point set information

Overrides:
toString in class DigitalNetBase2

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

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