V. labo.

Class FaureSequence

  extended by umontreal.iro.lecuyer.hups.PointSet
      extended by umontreal.iro.lecuyer.hups.DigitalNet
          extended by umontreal.iro.lecuyer.hups.DigitalSequence
              extended by umontreal.iro.lecuyer.hups.FaureSequence
Direct Known Subclasses:

public class FaureSequence
extends DigitalSequence

This class implements digital nets or digital sequences formed by the first n = bk points of the Faure sequence in base b. Values of n up to 231 are allowed. One has r = k. The generator matrices are

Cj = Pj mod b

for j = 0,..., s - 1, where P is a k×k upper triangular matrix whose entry (l, c) is the number of combinations of l objects among c, for l <= c and is 0 for l > c. The matrix C0 is the identity, C1 = P, and the other Cj's can be defined recursively via Cj = PCj-1mod b. Our implementation uses the recursion

Combination(c, l )  =  Combination(c - 1, l )   +  Combination(c - 1, l - 1)

to evaluate the binomial coefficients in the matrices Cj, as suggested by Fox. The entries xj, l, c of Cj are computed as follows:

xj, c, c = 1      for c = 0,..., k - 1,
xj, 0, c = jxj, 0, c-1      for c = 1,..., k - 1,
xj, l, c = xj, l-1, c-1 + jxj, l, c-1      for 2 <= c < l <= k - 1,
xj, l, c = 0      for c > l or l >= k.

For any integer m > 0 and ν >=  0, if we look at the vector (ui, j, 1,..., ui, j, m) (the first m digits of coordinate j of the output) when i goes from νbm to (ν +1)bm - 1, this vector takes each of its bm possible values exactly once. In particular, for ν = 0, ui, j visits each value in the set {0, 1/bm, 2/bm,...,(bm -1)/bm} exactly once, so all one-dimensional projections of the point set are identical. However, the values are visited in a different order for the different values of j (otherwise all coordinates would be identical). For j = 0, they are visited in the same order as in the van der Corput sequence in base b.

An important property of Faure nets is that for any integers m > 0 and ν >=  0, the point set {ui for i = νbm,...,(ν +1)bm -1} is a (0, m, s)-net in base b. In particular, for n = bk, the first n points form a (0, k, s)-net in base b. The Faure nets are also projection-regular and dimension-stationary.

To obtain digital nets from the generalized Faure sequence , where Pj is left-multiplied by some invertible matrix Aj, it suffices to apply an appropriate matrix scramble (e.g., via leftMatrixScramble). This changes the order in which ui, j visits its different values, for each coordinate j, but does not change the set of values that are visited. The (0, m, s)-net property stated above remains valid.

Constructor Summary
FaureSequence(int n, int dim)
          Same as FaureSequence(b, k, w, w, dim) with base b equal to the smallest prime larger or equal to dim, and with at least n points.
FaureSequence(int b, int k, int r, int w, int dim)
          Constructs a digital net in base b, with n = bk points and w output digits, in dim dimensions.
Method Summary
 void extendSequence(int k)
          Increases the number of points to n = bk from now on.
 String toString()
          Formats a string that contains information about the point set.
Methods inherited from class umontreal.iro.lecuyer.hups.DigitalSequence
iteratorShift, iteratorShiftNoGray, toNet, toNetShiftCj
Methods inherited from class umontreal.iro.lecuyer.hups.DigitalNet
addRandomShift, addRandomShift, clearRandomShift, eraseOriginalGeneratorMatrices, getCoordinate, getCoordinateNoGray, iBinomialMatrixScramble, iBinomialMatrixScrambleFaurePermut, iBinomialMatrixScrambleFaurePermutAll, iBinomialMatrixScrambleFaurePermutDiag, iterator, iteratorNoGray, leftMatrixScramble, leftMatrixScrambleDiag, leftMatrixScrambleFaurePermut, leftMatrixScrambleFaurePermutAll, leftMatrixScrambleFaurePermutDiag, printGeneratorMatrices, resetGeneratorMatrices, rightMatrixScramble, stripedMatrixScramble, stripedMatrixScrambleFaurePermutAll, 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


public FaureSequence(int b,
                     int k,
                     int r,
                     int w,
                     int dim)
Constructs a digital net in base b, with n = bk points and w output digits, in dim dimensions. The points are the first n points of the Faure sequence. The generator matrices Cj are r×k. Unless, one plans to apply a randomization on more than k digits (e.g., a random digital shift for w > k digits, or a linear scramble yielding r > k digits), one should take w = r = k for better computational efficiency. Restrictions: dim  <= 500 and bk <= 231.

b - base
k - there will be b^k points
r - number of rows in the generator matrices
w - number of output digits
dim - dimension of the point set


public FaureSequence(int n,
                     int dim)
Same as FaureSequence(b, k, w, w, dim) with base b equal to the smallest prime larger or equal to dim, and with at least n points. The values of k, r, and w are taken as k = ceil(logbn) and r = w = max(k, floor(30/log2b)).

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


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

toString in class DigitalNet
string representation of the point set information


public void extendSequence(int k)
Description copied from class: DigitalSequence
Increases the number of points to n = bk from now on.

Specified by:
extendSequence in class DigitalSequence
k - there will be b^k points

V. labo.

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