Overview | Package | Class | Tree | Deprecated | Index | Help
| SSJ V. 2.1.1.
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## umontreal.iro.lecuyer.hups
Class DigitalNet

    java.lang.Object
      umontreal.iro.lecuyer.hups.PointSet
          umontreal.iro.lecuyer.hups.DigitalNet

Direct Known Subclasses:
  DigitalNetBase2, DigitalNetFromFile, DigitalSequence

    public class DigitalNet

extends PointSet

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 | = | ∑r=0k-1ai, rbr, |
(ui, j, 1 ui, j, 2 …)T | = | Cj (ai, 0 ai, 1 … ai, k-1)T, |
ui, j | = | ∑r=1∞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.

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. 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. In practice, the digital shift is truncated to w digits, for some integer w >= r. Applying a digital shift does not change the equidistribution and (t, m, s)-net properties of a point set. 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, 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. 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 `resetCurPointIndex` or reinstantiated by the `iterator` method (this is not done automatically).

Constructor Summary
`DigitalNet()` Empty constructor.

Method Summary
`void` | `addRandomShift(int d1, int d2, RandomStream stream)` Adds a random digital shift to all the points of the point set, using stream `stream` to generate the random numbers.
`void` | `addRandomShift(RandomStream stream)` Same as `addRandomShift``(0, dim, stream)`, where `dim` is the dimension of the digital net.
`void` | `clearRandomShift()` Erases the current random shift, if any.
`void` | `eraseOriginalGeneratorMatrices()` Erases the original generator matrices and replaces them by the current ones.
`double` | `getCoordinate(int i, int j)` Returns ui, j, the coordinate j of the point i.
`double` | `getCoordinateNoGray(int i, int j)` Returns ui, j, the coordinate j of point i, the points being enumerated in the standard order (no Gray code).
`void` | `iBinomialMatrixScramble(RandomStream stream)` Applies the i-binomial matrix scramble proposed by Tezuka .
`void` | `iBinomialMatrixScrambleFaurePermut(RandomStream stream, int sb)` Similar to `iBinomialMatrixScramble` except that the diagonal elements of each matrix Mj are chosen as in `leftMatrixScrambleFaurePermut`.
`void` | `iBinomialMatrixScrambleFaurePermutAll(RandomStream stream, int sb)` Similar to `iBinomialMatrixScrambleFaurePermut` except that the elements under the diagonal are also chosen from the same restricted set as the diagonal elements.
`void` | `iBinomialMatrixScrambleFaurePermutDiag(RandomStream stream, int sb)` Similar to `iBinomialMatrixScrambleFaurePermut` except that all the off-diagonal elements are 0.
`PointSetIterator` | `iterator()` Constructs and returns a point set iterator.
`PointSetIterator` | `iteratorNoGray()` This iterator does not use the Gray code.
`void` | `leftMatrixScramble(RandomStream stream)` Applies a linear scramble by multiplying each Cj on the left by a w×w nonsingular lower-triangular matrix Mj, as suggested by Matoušek and implemented by Hong and Hickernell.
`void` | `leftMatrixScrambleDiag(RandomStream stream)` Similar to `leftMatrixScramble` except that all the off-diagonal elements of the Mj are 0.
`void` | `leftMatrixScrambleFaurePermut(RandomStream stream, int sb)` Similar to `leftMatrixScramble` except that the diagonal elements of each matrix Mj are chosen from a restricted set of the best integers as calculated by Faure.
`void` | `leftMatrixScrambleFaurePermutAll(RandomStream stream, int sb)` Similar to `leftMatrixScrambleFaurePermut` except that the elements under the diagonal are also chosen from the same restricted set as the diagonal elements.
`void` | `leftMatrixScrambleFaurePermutDiag(RandomStream stream, int sb)` Similar to `leftMatrixScrambleFaurePermut` except that all off-diagonal elements are 0.
`void` | `leftMatrixScrambleRest(RandomStream stream, int sb)` Deprecated.
`void` | `printGeneratorMatrices(int s)` Prints the generator matrices in standard form for dimensions 1 to s.
`void` | `resetGeneratorMatrices()` Restores the original generator matrices.
`void` | `rightMatrixScramble(RandomStream stream)` Applies a linear scramble by multiplying each Cj on the right by a single k×k nonsingular upper-triangular matrix M, as suggested by Faure and Tezuka.
`void` | `stripedMatrixScramble(RandomStream stream)` Applies the striped matrix scramble proposed by Owen.
`void` | `stripedMatrixScrambleFaurePermutAll(RandomStream stream, int sb)` Similar to `stripedMatrixScramble` except that the elements on and under the diagonal of each matrix Mj are chosen as in `leftMatrixScrambleFaurePermut`.
`String` | `toString()` Formats a string that contains the information about the point set.
`void` | `unrandomize()` By default, this method simply calls `clearRandomShift()`.

Methods inherited from class umontreal.iro.lecuyer.hups.PointSet
`addRandomShift, addRandomShift, formatPoints, formatPoints, 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()

  Empty constructor.

Method Detail

### getCoordinate

    public double getCoordinate(int i,
                                int j)

  Description copied from class: `PointSet`
  Returns ui, j, the coordinate j of the point i.

  Specified by:
    `getCoordinate` in class `PointSet`
  Parameters:
    `i` - index of the point to look for
    `j` - index of the coordinate to look for
  Returns:
    the value of ui, j

### iterator

    public PointSetIterator iterator()

  Description copied from class: `PointSet`
  Constructs and returns a point set iterator. The default implementation returns an iterator that uses the method `getCoordinate` `(i,j)` to iterate over the points and coordinates, but subclasses can reimplement it for better efficiency.

  Overrides:
    `iterator` in class `PointSet`
  Returns:
    point set iterator for the point set

### getCoordinateNoGray

    public double getCoordinateNoGray(int i,
                                      int j)

  Returns ui, j, the coordinate j of point i, the points being enumerated in the standard order (no Gray code).

  Parameters:
    `i` - point index
    `j` - coordinate index
  Returns:
    the value of ui, j

### iteratorNoGray

    public PointSetIterator iteratorNoGray()

  This iterator does not use the Gray code. Thus the points are enumerated in the order of their first coordinate before randomization.

### addRandomShift

    public void addRandomShift(int d1,
                               int d2,
                               RandomStream stream)

  Adds a random digital shift to all the points of the point set, using stream `stream` to generate the random numbers. For each coordinate j from `d1` to `d2-1`, the shift vector (dj, 0,..., dj, k-1) is generated uniformly over {0,..., b - 1}k and added modulo b to the digits of all the points. After adding a digital shift, all iterators must be reconstructed or reset to zero.

  Overrides:
    `addRandomShift` in class `PointSet`
  Parameters:
    `stream` - random number stream used to generate uniforms

### addRandomShift

    public void addRandomShift(RandomStream stream)

  Same as `addRandomShift``(0, dim, stream)`, where `dim` is the dimension of the digital net.

  Overrides:
    `addRandomShift` in class `PointSet`
  Parameters:
    `stream` - random number stream used to generate uniforms

### clearRandomShift

    public void clearRandomShift()

  Description copied from class: `PointSet`
  Erases the current random shift, if any.

  Overrides:
    `clearRandomShift` in class `PointSet`

### toString

    public String toString()

  Description copied from class: `PointSet`
  Formats a string that contains the information about the point set.

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

### leftMatrixScramble

    public void leftMatrixScramble(RandomStream stream)

  Applies a linear scramble by multiplying each Cj on the left by a w×w nonsingular lower-triangular matrix Mj, as suggested by Matoušek and implemented by Hong and Hickernell. The diagonal entries of each matrix Mj are generated uniformly over {1,..., b - 1}, the entries below the diagonal are generated uniformly over {0,..., b - 1}, and all these entries are generated independently. This means that in base b = 2, all diagonal elements are equal to 1.

  Parameters:
    `stream` - random number stream used to generate the randomness

### leftMatrixScrambleDiag

    public void leftMatrixScrambleDiag(RandomStream stream)

  Similar to `leftMatrixScramble` except that all the off-diagonal elements of the Mj are 0.

  Parameters:
    `stream` - random number stream used to generate the randomness

### leftMatrixScrambleFaurePermut

    public void leftMatrixScrambleFaurePermut(RandomStream stream,
                                              int sb)

  Similar to `leftMatrixScramble` except that the diagonal elements of each matrix Mj are chosen from a restricted set of the best integers as calculated by Faure. They are generated uniformly over the first `sb` elements of array F, where F is made up of a permutation of the integers [1..(b - 1)]. These integers are sorted by increasing order of the upper bounds of the extreme discrepancy for the given integer.

  Parameters:
    `stream` - random number stream used to generate the randomness
    `sb` - Only the first sb elements of F are used

### leftMatrixScrambleRest

    @Deprecated
    public void leftMatrixScrambleRest(RandomStream stream,
                                                  int sb)

  Deprecated.

### leftMatrixScrambleFaurePermutDiag

    public void leftMatrixScrambleFaurePermutDiag(RandomStream stream,
                                                  int sb)

  Similar to `leftMatrixScrambleFaurePermut` except that all off-diagonal elements are 0.

  Parameters:
    `stream` - random number stream used to generate the randomness
    `sb` - Only the first sb elements of F are used

### leftMatrixScrambleFaurePermutAll

    public void leftMatrixScrambleFaurePermutAll(RandomStream stream,
                                                 int sb)

  Similar to `leftMatrixScrambleFaurePermut` except that the elements under the diagonal are also chosen from the same restricted set as the diagonal elements.

  Parameters:
    `stream` - random number stream used to generate the randomness
    `sb` - Only the first sb elements of F are used

### iBinomialMatrixScramble

    public void iBinomialMatrixScramble(RandomStream stream)

  Applies the i-binomial matrix scramble proposed by Tezuka . This multiplies each Cj on the left by a w×w nonsingular lower-triangular matrix Mj as in `leftMatrixScramble`, but with the additional constraint that all entries on any given diagonal or subdiagonal of Mj are identical.

  Parameters:
    `stream` - random number stream used as generator of the randomness

### iBinomialMatrixScrambleFaurePermut

    public void iBinomialMatrixScrambleFaurePermut(RandomStream stream,
                                                   int sb)

  Similar to `iBinomialMatrixScramble` except that the diagonal elements of each matrix Mj are chosen as in `leftMatrixScrambleFaurePermut`.

  Parameters:
    `stream` - random number stream used to generate the randomness
    `sb` - Only the first sb elements of F are used

### iBinomialMatrixScrambleFaurePermutDiag

    public void iBinomialMatrixScrambleFaurePermutDiag(RandomStream stream,
                                                       int sb)

  Similar to `iBinomialMatrixScrambleFaurePermut` except that all the off-diagonal elements are 0.

  Parameters:
    `stream` - random number stream used to generate the randomness
    `sb` - Only the first sb elements of F are used

### iBinomialMatrixScrambleFaurePermutAll

    public void iBinomialMatrixScrambleFaurePermutAll(RandomStream stream,
                                                      int sb)

  Similar to `iBinomialMatrixScrambleFaurePermut` except that the elements under the diagonal are also chosen from the same restricted set as the diagonal elements.

  Parameters:
    `stream` - random number stream used to generate the randomness
    `sb` - Only the first sb elements of F are used

### stripedMatrixScramble

    public void stripedMatrixScramble(RandomStream stream)

  Applies the striped matrix scramble proposed by Owen. It multiplies each Cj on the left by a w×w nonsingular lower-triangular matrix Mj as in `leftMatrixScramble`, but with the additional constraint that in any column, all entries below the diagonal are equal to the diagonal entry, which is generated randomly over {1,..., b - 1}. Note that for b = 2, the matrices Mj become deterministic, with all entries on and below the diagonal equal to 1.

  Parameters:
    `stream` - random number stream used as generator of the randomness

### stripedMatrixScrambleFaurePermutAll

    public void stripedMatrixScrambleFaurePermutAll(RandomStream stream,
                                                    int sb)

  Similar to `stripedMatrixScramble` except that the elements on and under the diagonal of each matrix Mj are chosen as in `leftMatrixScrambleFaurePermut`.

  Parameters:
    `stream` - random number stream used as generator of the randomness
    `sb` - Only the first sb elements of F are used

### rightMatrixScramble

    public void rightMatrixScramble(RandomStream stream)

  Applies a linear scramble by multiplying each Cj on the right by a single k×k nonsingular upper-triangular matrix M, as suggested by Faure and Tezuka. The diagonal entries of the matrix M are generated uniformly over {1,..., b - 1}, the entries above the diagonal are generated uniformly over {0,..., b - 1}, and all the entries are generated independently. The effect of this scramble is only to change the order in which the points are generated. If one computes the average value of a function over all the points of a given digital net, or over a number of points that is a power of the basis, then this scramble makes no difference.

  Parameters:
    `stream` - random number stream used as generator of the randomness

### unrandomize

    public void unrandomize()

  Description copied from class: `PointSet`
  By default, this method simply calls `clearRandomShift()`.

  Overrides:
    `unrandomize` in class `PointSet`

### resetGeneratorMatrices

    public void resetGeneratorMatrices()

  Restores the original generator matrices. This removes the current linear matrix scrambles.

### eraseOriginalGeneratorMatrices

    public void eraseOriginalGeneratorMatrices()

  Erases the original generator matrices and replaces them by the current ones. The current linear matrix scrambles thus become permanent. This is useful if we want to apply several scrambles in succession to a given digital net.

### printGeneratorMatrices

    public void printGeneratorMatrices(int s)

  Prints the generator matrices in standard form for dimensions 1 to s.

Overview | Package | Class | Tree | Deprecated | Index | Help
| SSJ V. 2.1.1.
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

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