SSJ  3.2.1
Stochastic Simulation in Java
Public Member Functions | Static Package Attributes | List of all members
FaureSequence Class Reference

This class implements digital nets or digital sequences formed by the first \(n = b^k\) points of the Faure sequence in base \(b\). More...

Inheritance diagram for FaureSequence:
[legend]
Collaboration diagram for FaureSequence:
[legend]

Public Member Functions

 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. More...
 
 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. More...
 
String toString ()
 
void extendSequence (int k)
 
- Public Member Functions inherited from DigitalSequence
abstract void extendSequence (int k)
 Increases the number of points to \(n = b^k\) from now on. More...
 
DigitalNet toNet ()
 Transforms this digital sequence into a digital net without changing the coordinates of the points. More...
 
DigitalNet toNetShiftCj ()
 Transforms this digital sequence into a digital net by adding one dimension and shifting all coordinates by one position. More...
 
PointSetIterator iteratorShift ()
 Similar to #iterator, except that the first coordinate of the points is \(i/n\), the second coordinate is obtained via the generating matrix \(\mathbf{C}_0\), the next one via \(\mathbf{C}_1\), and so on. More...
 
PointSetIterator iteratorShiftNoGray ()
 This iterator shifts all coordinates of each point one position to the right and sets the first coordinate of point \(i\) to \(i/n\), so that the points enumerated with this iterator have one more dimension. More...
 
- Public Member Functions inherited from DigitalNet
double getCoordinate (int i, int j)
 
PointSetIterator iterator ()
 
 DigitalNet ()
 Empty constructor.
 
double getCoordinateNoGray (int i, int j)
 Returns \(u_{i,j}\), the coordinate \(j\) of point \(i\), the points being enumerated in the standard order (no Gray code). More...
 
PointSetIterator iteratorNoGray ()
 This iterator does not use the Gray code. More...
 
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. More...
 
void addRandomShift (RandomStream stream)
 Same as addRandomShift(0, dim, stream), where dim is the dimension of the digital net. More...
 
void clearRandomShift ()
 Erases the current digital random shift, if any.
 
String toString ()
 
void leftMatrixScramble (RandomStream stream)
 Applies a linear scramble by multiplying each \(\mathbf{C}_j\) on the left by a \(w\times w\) nonsingular lower-triangular matrix \(\mathbf{M}_j\), as suggested by Matoušek [169]  and implemented by Hong and Hickernell [86] . More...
 
void leftMatrixScrambleDiag (RandomStream stream)
 Similar to leftMatrixScramble except that all the off-diagonal elements of the \(\mathbf{M}_j\) are 0. More...
 
void leftMatrixScrambleFaurePermut (RandomStream stream, int sb)
 Similar to leftMatrixScramble except that the diagonal elements of each matrix \(\mathbf{M}_j\) are chosen from a restricted set of the best integers as calculated by Faure [56] . More...
 
void leftMatrixScrambleFaurePermutDiag (RandomStream stream, int sb)
 Similar to leftMatrixScrambleFaurePermut except that all off-diagonal elements are 0. More...
 
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. More...
 
void iBinomialMatrixScramble (RandomStream stream)
 Applies the \(i\)-binomial matrix scramble proposed by Tezuka [217]  (see also [184] ). More...
 
void iBinomialMatrixScrambleFaurePermut (RandomStream stream, int sb)
 Similar to iBinomialMatrixScramble except that the diagonal elements of each matrix \(\mathbf{M}_j\) are chosen as in leftMatrixScrambleFaurePermut. More...
 
void iBinomialMatrixScrambleFaurePermutDiag (RandomStream stream, int sb)
 Similar to iBinomialMatrixScrambleFaurePermut except that all the off-diagonal elements are 0. More...
 
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. More...
 
void stripedMatrixScramble (RandomStream stream)
 Applies the striped matrix scramble proposed by Owen [184] . More...
 
void stripedMatrixScrambleFaurePermutAll (RandomStream stream, int sb)
 Similar to stripedMatrixScramble except that the elements on and under the diagonal of each matrix \(\mathbf{M}_j\) are chosen as in leftMatrixScrambleFaurePermut. More...
 
void rightMatrixScramble (RandomStream stream)
 Applies a linear scramble by multiplying each \(\mathbf{C}_j\) on the right by a single \(k\times k\) nonsingular upper-triangular matrix \(\mathbf{M}\), as suggested by Faure and Tezuka [56]  (see also [86] ). More...
 
void unrandomize ()
 Restores the original generator matrices and removes the random shift.
 
void resetGeneratorMatrices ()
 Restores the original generator matrices. More...
 
void eraseOriginalGeneratorMatrices ()
 Erases the original generator matrices and replaces them by the current ones. More...
 
void printGeneratorMatrices (int s)
 Prints the generator matrices in standard form for dimensions 1 to \(s\).
 
- Public Member Functions inherited from PointSet
int getDimension ()
 Returns the dimension (number of available coordinates) of the point set. More...
 
int getNumPoints ()
 Returns the number of points. More...
 
abstract double getCoordinate (int i, int j)
 Returns \(u_{i,j}\), the coordinate \(j\) of the point \(i\). More...
 
PointSetIterator iterator ()
 Constructs and returns a point set iterator. More...
 
void setStream (RandomStream stream)
 Sets the random stream used to generate random shifts to stream. More...
 
RandomStream getStream ()
 Returns the random stream used to generate random shifts. More...
 
void randomize (PointSetRandomization rand)
 Randomizes the point set using the given rand. More...
 
void addRandomShift (int d1, int d2, RandomStream stream)
 This method does nothing for this generic class. More...
 
void addRandomShift (RandomStream stream)
 This method does nothing for this generic class. More...
 
void addRandomShift (int d1, int d2)
 Similar to addRandomShift(d1, d2, stream), with the current random stream.
 
void addRandomShift ()
 Similar to addRandomShift(0, d2, stream) with the current random stream and d2 the dimension of the current random shift.
 
void clearRandomShift ()
 Erases the current random shift, if any.
 
void randomize (int fromDim, int toDim, RandomStream stream)
 By default, this method simply calls addRandomShift (fromDim, toDim, stream), which does nothing.
 
void randomize (RandomStream stream)
 By default, this method simply calls randomize(0, dim, stream).
 
void randomize (int d1, int d2)
 By default, this method simply calls addRandomShift(d1, d2).
 
void randomize ()
 By default, this method simply calls addRandomShift().
 
void unrandomize ()
 By default, this method simply calls clearRandomShift().
 
String toString ()
 Formats a string that contains information about the point set. More...
 
String formatPoints ()
 Same as invoking formatPoints(n, d) with \(n\) and \(d\) equal to the number of points and the dimension of this object, respectively. More...
 
String formatPoints (int n, int d)
 Formats a string that displays the same information as returned by toString, together with the first \(d\) coordinates of the first \(n\) points. More...
 
String formatPoints (PointSetIterator iter)
 Same as invoking formatPoints(iter, n, d) with \(n\) and \(d\) equal to the number of points and the dimension, respectively. More...
 
String formatPoints (PointSetIterator iter, int n, int d)
 Same as invoking formatPoints(n, d), but prints the points by calling iter repeatedly. More...
 
String formatPointsBase (int b)
 Similar to formatPoints(), but the points coordinates are printed in base \(b\). More...
 
String formatPointsBase (int n, int d, int b)
 Similar to formatPoints(n, d), but the points coordinates are printed in base \(b\). More...
 
String formatPointsBase (PointSetIterator iter, int b)
 Similar to formatPoints(iter), but the points coordinates are printed in base \(b\). More...
 
String formatPointsBase (PointSetIterator iter, int n, int d, int b)
 Similar to formatPoints(iter, n, d), but the points coordinates are printed in base \(b\). More...
 
String formatPointsNumbered ()
 Same as invoking formatPointsNumbered(n, d) with \(n\) and \(d\) equal to the number of points and the dimension, respectively. More...
 
String formatPointsNumbered (int n, int d)
 Same as invoking formatPoints(n,d), except that the points are numbered. More...
 

Static Package Attributes

static final int primes []
 

Additional Inherited Members

- Protected Member Functions inherited from DigitalNet
int intToDigitsGray (int b, int i, int numDigits, int[] bary, int[] gray)
 
- Protected Attributes inherited from DigitalNet
int b = 0
 
int numCols = 0
 
int numRows = 0
 
int outDigits = 0
 
int [][] genMat
 
int [][] digitalShift
 
double normFactor
 
double [] factor
 
- Protected Attributes inherited from PointSet
double EpsilonHalf = 1.0 / Num.TWOEXP[55]
 
int dim = 0
 
int numPoints = 0
 
int dimShift = 0
 
int capacityShift = 0
 
RandomStream shiftStream
 
- Static Protected Attributes inherited from PointSet
static final int MAXBITS = 31
 

Detailed Description

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^{31}\) are allowed. One has \(r = k\). The generator matrices are

\[ \mathbf{C}_j = \mathbf{P}^j \mod b \]

for \(j=0,…,s-1\), where \(\mathbf{P}\) is a \(k\times k\) upper triangular matrix whose entry \((l,c)\) is the number of combinations of \(l\) objects among \(c\), \({c\choose l}\), for \(l\le c\) and is 0 for \(l > c\). The matrix \(\mathbf{C}_0\) is the identity, \(\mathbf{C}_1 = \mathbf{P}\), and the other \(\mathbf{C}_j\)’s can be defined recursively via \(\mathbf{C}_j = \mathbf{P} \mathbf{C}_{j-1} \mod b\). Our implementation uses the recursion

\[ {c \choose l} = {{c-1} \choose l} + {{c-1} \choose{l-1}} \]

to evaluate the binomial coefficients in the matrices \(\mathbf{C}_j\), as suggested by Fox [61]  (see also [67] , page 301). The entries \(x_{j,l,c}\) of \(\mathbf{C}_j\) are computed as follows:

\[ \begin{array}{lcll} x_{j,c,c} & = & 1 & \quad\mbox{ for } c=0,…,k-1, \\ x_{j,0,c} & = & j x_{j,0,c-1} & \quad\mbox{ for } c=1,…,k-1, \\ x_{j,l,c} & = & x_{j,l-1,c-1} + j x_{j,l,c-1} & \quad\mbox{ for } 2\le c < l \le k-1, \\ x_{j,l,c} & = & 0 & \quad\mbox{ for } c>l \mbox{ or } l \ge k. \end{array} \]

For any integer \(m > 0\) and \(\nu\ge0\), 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 \(\nu b^m\) to \((\nu+1)b^m - 1\), this vector takes each of its \(b^m\) possible values exactly once. In particular, for \(\nu= 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 \(\nu\ge0\), the point set \(\{\mathbf{u}_i\) for \(i = \nu b^m,…, (\nu+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 (see [124]  for definitions of these properties).

To obtain digital nets from the generalized Faure sequence [219] , where \(\mathbf{P}_j\) is left-multiplied by some invertible matrix \(\mathbf{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 & Destructor Documentation

◆ FaureSequence() [1/2]

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 \(\mathbf{C}_j\) are \(r\times 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 \(\le500\) and \(b^k \le2^{31}\).

Parameters
bbase
kthere will be b^k points
rnumber of rows in the generator matrices
wnumber of output digits
dimdimension of the point set

◆ FaureSequence() [2/2]

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 = \lceil\log_b n\rceil\) and \(r = w = \max(k, \lfloor30 / \log_2 b\rfloor)\).

Parameters
nminimal number of points
dimdimension of the point set

Member Data Documentation

◆ primes

final int primes[]
staticpackage
Initial value:
=
{2,2,3,5,5,7,7,11,11,11,11,13,13,17,17,17,17,19,19,23,
23,23,23,29,29,29,29,29,29,31,31,37,37,37,37,37,37,41,41,41,
41,43,43,47,47,47,47,53,53,53,53,53,53,59,59,59,59,59,59,61,
61,67,67,67,67,67,67,71,71,71,71,73,73,79,79,79,79,79,79,83,
83,83,83,89,89,89,89,89,89,97,97,97,97,97,97,97,97,101,101,101,
101,103,103,107,107,107,107,109,109,113,113,113,113,127,127,127,127,127,127,127,
127,127,127,127,127,127,127,131,131,131,131,137,137,137,137,137,137,139,139,149,
149,149,149,149,149,149,149,149,149,151,151,157,157,157,157,157,157,163,163,163,
163,163,163,167,167,167,167,173,173,173,173,173,173,179,179,179,179,179,179,181,
181,191,191,191,191,191,191,191,191,191,191,193,193,197,197,197,197,199,199,211,
211,211,211,211,211,211,211,211,211,211,211,223,223,223,223,223,223,223,223,223,
223,223,223,227,227,227,227,229,229,233,233,233,233,239,239,239,239,239,239,241,
241,251,251,251,251,251,251,251,251,251,251,257,257,257,257,257,257,263,263,263,
263,263,263,269,269,269,269,269,269,271,271,277,277,277,277,277,277,281,281,281,
281,283,283,293,293,293,293,293,293,293,293,293,293,307,307,307,307,307,307,307,
307,307,307,307,307,307,307,311,311,311,311,313,313,317,317,317,317,331,331,331,
331,331,331,331,331,331,331,331,331,331,331,337,337,337,337,337,337,347,347,347,
347,347,347,347,347,347,347,349,349,353,353,353,353,359,359,359,359,359,359,367,
367,367,367,367,367,367,367,373,373,373,373,373,373,379,379,379,379,379,379,383,
383,383,383,389,389,389,389,389,389,397,397,397,397,397,397,397,397,401,401,401,
401,409,409,409,409,409,409,409,409,419,419,419,419,419,419,419,419,419,419,421,
421,431,431,431,431,431,431,431,431,431,431,433,433,439,439,439,439,439,439,443,
443,443,443,449,449,449,449,449,449,457,457,457,457,457,457,457,457,461,461,461,
461,463,463,467,467,467,467,479,479,479,479,479,479,479,479,479,479,479,479,487,
487,487,487,487,487,487,487,491,491,491,491,499,499,499,499,499,499,499,499,503}

The documentation for this class was generated from the following file: