SSJ
V. labo.

umontreal.iro.lecuyer.hups
Class DigitalNet

java.lang.Object
  extended by umontreal.iro.lecuyer.hups.PointSet
      extended by umontreal.iro.lecuyer.hups.DigitalNet
Direct Known Subclasses:
DigitalNetBase2, DigitalNetFromFile, DigitalSequence

public class DigitalNet
extends PointSet

DigitalNet

This class provides the basic structures for storing and manipulating linear digital nets in base b, for an arbitrary base b≥2. We recall that a net contains n = bk points in s dimensions, where the ith point ui, for i = 0,..., bk - 1, is defined as follows:

i      =      $\displaystyle \htsum_{{r=0}}^{{k-1}}$ai, rbr,  
(ui, j, 1 ui, j, 2 …)T      =      Cj (ai, 0 ai, 1 … ai, k-1)T,  
ui, j      =      $\displaystyle \htsum_{{r=1}}^{\infty}$ui, j, rb-r,  
ui      =      (ui, 0, …, ui, s-1).  

In our implementation, the matrices Cj are r×k, so the expansion of ui, j is truncated to its first r terms. The points are stored implicitly by storing the generator matrices Cj in a large two-dimensional array of integers, with srk elements.
\begin{detailed}
 For general $b$, the element $(l,c)$\ of $\mathbf{C}_j$\ (count...
 ...ements
 from 0) is stored at position $[jk+c][l]$\ in this array.
 \end{detailed}

The points ui are enumerated using the Gray code technique. With this technique, the b-ary representation of i, ai = (ai, 0,..., ai, k-1), is replaced by a Gray code representation of i, gi = (gi, 0,..., gi, k-1). The Gray code gi used here is defined by gi, k-1 = ai, k-1 and gi, ν = (ai, ν - ai, ν+1)mod b for ν = 0,..., k - 2. It has the property that gi = (gi, 0,..., gi, k-1) and gi+1 = (gi+1, 0,..., gi+1, k-1) differ only in the position of the smallest index ν such that ai, ν < b - 1, and we have gi+1, ν = (gi, ν +1)mod b in that position.

This Gray code representation permits a more efficient enumeration of the points by the iterators. It changes the order in which the points ui are enumerated, but the first bm points remain the same for every integer m. The ith point of the sequence with the Gray enumeration is the i'th point of the original enumeration, where i' is the integer whose b-ary representation ai' is given by the Gray code gi. To enumerate all the points successively, we never need to compute the Gray codes explicitly. It suffices to know the position ν of the Gray code digit that changes at each step, and this can be found quickly from the b-ary representation ai. The digits of each coordinate j of the current point can be updated by adding column ν of the generator matrix Cj to the old digits, modulo b.

One should avoid using the method getCoordinate(i, j) for arbitrary values of i and j, because this is much slower than using an iterator to access successive coordinates.

Digital nets can be randomized in various ways[#!mMAT99a!#,#!rFAU02a!#,#!vLEC02a!#,#!vOWE03a!#]. Several types of randomizations specialized for nets are implemented directly in this class.

A simple but important randomization is the random digital shift in base b, defined as follows: replace each digit ui, j, ν in the third equation above by (ui, j, ν + dj, ν)mod b, where the dj, ν's are i.i.d. uniform over {0,..., b - 1}. This is equivalent to applying a single random shift to all the points in a formal series representation of their coordinates[#!vLEC02a!#,#!vLEM03a!#]. In practice, the digital shift is truncated to w digits, for some integer wr. Applying a digital shift does not change the equidistribution and (t, m, s)-net properties of a point set[#!vHON03a!#,#!vLEC99a!#,#!vLEM03a!#]. Moreover, with the random shift, each point is uniformly distributed over the unit hypercube (but the points are not independent, of course).

A second class of randomizations specialized for digital nets are the linear matrix scrambles[#!mMAT99a!#,#!rFAU02a!#,#!vHON03a!#,#!vOWE03a!#], which multiply the matrices Cj by a random invertible matrix Mj, modulo b. There are several variants, depending on how Mj is generated, and on whether Cj is multiplied on the left or on the right. In our implementation, the linear matrix scrambles are incorporated directly into the matrices Cj, so they do not slow down the enumeration of points. Methods are available for applying linear matrix scrambles and for removing these randomizations. These methods generate the appropriate random numbers and make the corresponding changes to the Cj's. A copy of the original Cj's is maintained, so the point set can be returned to its original unscrambled state at any time. When a new linear matrix scramble is applied, it is always applied to the original generator matrices. The method resetGeneratorMatrices removes the current matrix scramble by resetting the generator matrices to their original state. On the other hand, the method eraseOriginalGeneratorMatrices replaces the original generator matrices by the current ones, making the changes permanent. This is useful if one wishes to apply two or more linear matrix scrambles on top of each other.

Linear matrix scrambles are usually combined with a random digital shift; this combination is called an affine matrix scramble[#!vOWE03a!#]. These two randomizations are applied via separate methods. The linear matrix scrambles are incorporated into the matrices Cj whereas the digital random shift is stored and applied separately, independently of the other scramblings.

Applying a digital shift or a linear matrix scramble to a digital net invalidates all iterators for that randomized point, because each iterator uses a cached copy of the current point, which is updated only when the current point index of that iterator changes, and the update also depends on the cached copy of the previous point. After applying any kind of scrambling, the iterators must be reinitialized to the initial point by invoking PointSetIteratorresetCurPointIndex or reinstantiated by the iterator method (this is not done automatically).


Constructor Summary
DigitalNet()
          .
 
Method Summary
 void addRandomShift(int d1, int d2, RandomStream stream)
          .
 void addRandomShift(RandomStream stream)
          .
 void clearRandomShift()
          .
 void eraseOriginalGeneratorMatrices()
          .
 double getCoordinate(int i, int j)
          .
 double getCoordinateNoGray(int i, int j)
          .
 void iBinomialMatrixScramble(RandomStream stream)
          .
 void iBinomialMatrixScrambleFaurePermut(RandomStream stream, int sb)
          .
 void iBinomialMatrixScrambleFaurePermutAll(RandomStream stream, int sb)
          .
 void iBinomialMatrixScrambleFaurePermutDiag(RandomStream stream, int sb)
          .
 PointSetIterator iterator()
          .
 PointSetIterator iteratorNoGray()
          .
 void leftMatrixScramble(RandomStream stream)
          .
 void leftMatrixScrambleDiag(RandomStream stream)
          .
 void leftMatrixScrambleFaurePermut(RandomStream stream, int sb)
          .
 void leftMatrixScrambleFaurePermutAll(RandomStream stream, int sb)
          .
 void leftMatrixScrambleFaurePermutDiag(RandomStream stream, int sb)
          .
 void printGeneratorMatrices(int s)
          .
 void resetGeneratorMatrices()
          .
 void rightMatrixScramble(RandomStream stream)
          .
 void stripedMatrixScramble(RandomStream stream)
          .
 void stripedMatrixScrambleFaurePermutAll(RandomStream stream, int sb)
          .
 String toString()
          .
 void 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

DigitalNet

public DigitalNet()
. \begin{tabb}Empty constructor.
 \end{tabb}

Method Detail

getCoordinate

public double getCoordinate(int i,
                            int j)
Description copied from class: PointSet
. \begin{tabb}
 Returns $u_{i,j}$, the coordinate $j$\ of the point $i$.
 \richard{...
 ...xttt{getCoordinate} impl\'ementent le random shift
 quand il existe?}
 \end{tabb}
iindex of the point to look for jindex of the coordinate to look for the value of ui, j

Specified by:
getCoordinate in class PointSet

iterator

public PointSetIterator iterator()
Description copied from class: PointSet
. \begin{tabb}
 Constructs and returns a point set iterator.
 The default implemen...
 ...oordinates, but subclasses can reimplement it
 for better efficiency.
 \end{tabb}
point set iterator for the point set

Overrides:
iterator in class PointSet

getCoordinateNoGray

public double getCoordinateNoGray(int i,
                                  int j)
. \begin{tabb}
 Returns $u_{i,j}$, the coordinate $j$\ of point $i$, the points
 being enumerated in the standard order (no Gray code).
 \end{tabb}
ipoint index jcoordinate index the value of ui, j


iteratorNoGray

public PointSetIterator iteratorNoGray()
. \begin{tabb}
 This iterator does not use the Gray code. Thus the points are enumerated
 in the order of their first coordinate before randomization.
 \end{tabb}


addRandomShift

public void addRandomShift(int d1,
                           int d2,
                           RandomStream stream)
. \begin{tabb}Adds a random digital shift to all the points of the point set,
 usi...
 ...digital shift, all iterators must be reconstructed or
 reset to zero.
 \end{tabb}
streamrandom number stream used to generate uniforms

Overrides:
addRandomShift in class PointSet

addRandomShift

public void addRandomShift(RandomStream stream)
. \begin{tabb}Same as \method{addRandomShift}{}\texttt{(0, dim, stream)},
 where \texttt{dim} is the dimension of the digital net.
 \end{tabb}
streamrandom number stream used to generate uniforms
 

Overrides:
addRandomShift in class PointSet

clearRandomShift

public void clearRandomShift()
. \begin{hide}
 \par
 \begin{tabb}
 Erases the current digital random shift, if any.
 \end{tabb}\end{hide}

Overrides:
clearRandomShift in class PointSet

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 PointSet

leftMatrixScramble

public void leftMatrixScramble(RandomStream stream)
. \begin{tabb}
 Applies a linear scramble by multiplying each $\mathbf{C}_j$\ on t...
 ...pouvoir
 randomiser plus les derniers chiffres ou les derniers bits.}
 \end{tabb}
streamrandom number stream used to generate the randomness


leftMatrixScrambleDiag

public void leftMatrixScrambleDiag(RandomStream stream)
. \begin{tabb}
 Similar to \method{leftMatrixScramble}{} except that all the
 off-diagonal elements of the $\mathbf{M}_j$\ are 0.
 \end{tabb}
streamrandom number stream used to generate the randomness


leftMatrixScrambleFaurePermut

public void leftMatrixScrambleFaurePermut(RandomStream stream,
                                          int sb)
. \begin{tabb}
 Similar to \method{leftMatrixScramble}{} except that the diagonal ...
 ...f the upper bounds of the extreme discrepancy
 for the given integer.
 \end{tabb}
streamrandom number stream used to generate the randomness sbOnly the first sb elements of F are used


leftMatrixScrambleFaurePermutDiag

public void leftMatrixScrambleFaurePermutDiag(RandomStream stream,
                                              int sb)
. \begin{tabb}
 Similar to \method{leftMatrixScrambleFaurePermut}{} except that all
 off-diagonal elements are 0.
 \end{tabb}
streamrandom number stream used to generate the randomness sbOnly the first sb elements of F are used


leftMatrixScrambleFaurePermutAll

public void leftMatrixScrambleFaurePermutAll(RandomStream stream,
                                             int sb)
. \begin{tabb}
 Similar to \method{leftMatrixScrambleFaurePermut}{} except that th...
 ...e also
 chosen from the same restricted set as the diagonal elements.
 \end{tabb}
streamrandom number stream used to generate the randomness sbOnly the first sb elements of F are used


iBinomialMatrixScramble

public void iBinomialMatrixScramble(RandomStream stream)
. \begin{tabb}
 Applies the $i$-binomial matrix scramble proposed by Tezuka\cite{r...
 ...n any given diagonal or subdiagonal of $\mathbf{M}_j$\ are identical.
 \end{tabb}
streamrandom number stream used as generator of the randomness


iBinomialMatrixScrambleFaurePermut

public void iBinomialMatrixScrambleFaurePermut(RandomStream stream,
                                               int sb)
. \begin{tabb}
 Similar to \method{iBinomialMatrixScramble}{} except that the diag...
 ...bf{M}_j$\ are chosen as in
 \method{leftMatrixScrambleFaurePermut}{}.
 \end{tabb}
streamrandom number stream used to generate the randomness sbOnly the first sb elements of F are used


iBinomialMatrixScrambleFaurePermutDiag

public void iBinomialMatrixScrambleFaurePermutDiag(RandomStream stream,
                                                   int sb)
. \begin{tabb}
 Similar to \method{iBinomialMatrixScrambleFaurePermut}{} except that all the
 off-diagonal elements are 0.
 \end{tabb}
streamrandom number stream used to generate the randomness sbOnly the first sb elements of F are used


iBinomialMatrixScrambleFaurePermutAll

public void iBinomialMatrixScrambleFaurePermutAll(RandomStream stream,
                                                  int sb)
. \begin{tabb}
 Similar to \method{iBinomialMatrixScrambleFaurePermut}{} except th...
 ...e also
 chosen from the same restricted set as the diagonal elements.
 \end{tabb}
streamrandom number stream used to generate the randomness sbOnly the first sb elements of F are used


stripedMatrixScramble

public void stripedMatrixScramble(RandomStream stream)
. \begin{tabb}
 Applies the \emph{striped matrix scramble} proposed by Owen\cite{v...
 ...eterministic, with
 all entries on and below the diagonal equal to 1.
 \end{tabb}
streamrandom number stream used as generator of the randomness


stripedMatrixScrambleFaurePermutAll

public void stripedMatrixScrambleFaurePermutAll(RandomStream stream,
                                                int sb)
. \begin{tabb}
 Similar to \method{stripedMatrixScramble}{} except that the
 eleme...
 ...bf{M}_j$\ are
 chosen as in \method{leftMatrixScrambleFaurePermut}{}.
 \end{tabb}
streamrandom number stream used as generator of the randomness sbOnly the first sb elements of F are used


rightMatrixScramble

public void rightMatrixScramble(RandomStream stream)
. \begin{tabb}
 Applies a linear scramble by multiplying each $\mathbf{C}_j$\ on t...
 ...hat is a power of the basis, then this
 scramble makes no difference.
 \end{tabb}
streamrandom number stream used as generator of the randomness
\begin{hide}%
 \par
 \end{hide}


unrandomize

public void unrandomize()
. \begin{hide}
 \par
 \begin{tabb}
 Restores the original generator matrices and
 removes the random shift.
 \end{tabb}\end{hide}

Overrides:
unrandomize in class PointSet

resetGeneratorMatrices

public void resetGeneratorMatrices()
. \begin{tabb}
 Restores the original generator matrices.
 This removes the current linear matrix scrambles.
 \end{tabb}


eraseOriginalGeneratorMatrices

public void eraseOriginalGeneratorMatrices()
. \begin{tabb}
 Erases the original generator matrices and replaces them by
 the c...
 ...ant to apply several
 scrambles in succession to a given digital net.
 \end{tabb}


printGeneratorMatrices

public void printGeneratorMatrices(int s)
. \begin{tabb}
 Prints the generator matrices in standard form for dimensions 1 to $s$.
 \end{tabb}


SSJ
V. labo.

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