umontreal.iro.lecuyer.hups
Class FaureSequence

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

public class FaureSequence
extends DigitalSequence

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

C_j = P^j 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 C₀ is the identity, C₁ = P, and the other C_j's can be defined recursively via C_j = PC_j-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 C_j, as suggested by Fox. The entries x_{j, l, c} of C_j 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 (u_{i, j, 1},..., u_{i, j, m}) (the first m digits of coordinate j of the output) when i goes from νb^m to (ν +1)b^m - 1, this vector takes each of its b^m possible values exactly once. In particular, for ν = 0, u_{i, j} visits each value in the set {0, 1/b^m, 2/b^m,...,(b^m -1)/b^m} 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 {u_i for i = νb^m,...,(ν +1)b^m -1} is a (0, m, s)-net in base b. In particular, for n = b^k, 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 P_j is left-multiplied by some invertible matrix A_j, it suffices to apply an appropriate matrix scramble (e.g., via leftMatrixScramble). This changes the order in which u_{i, 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 = b^k 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

FaureSequence

public FaureSequence(int b,
                     int k,
                     int r,
                     int w,
                     int dim)

Constructs a digital net in base b, with n = b^k points and w output digits, in dim dimensions. The points are the first n points of the Faure sequence. The generator matrices C_j 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 b^k <= 2³¹.

Parameters:

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

FaureSequence

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(log_bn) and r = w = max(k, floor(30/log₂b)).

Parameters:

n - minimal number of points

dim - dimension of the point set

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 DigitalNet

Returns:

string representation of the point set information

extendSequence

public void extendSequence(int k)

Description copied from class: DigitalSequence

Increases the number of points to n = b^k from now on.

Specified by:

extendSequence in class DigitalSequence

Parameters:

k - there will be b^k points