This class implements digital nets and digital sequences in base 2 formed by the first \(n = 2^k\) points of a Sobol’ sequence [213], [rSOB76b]. More...
Public Member Functions | |
| SobolSequence (int k, int w, int dim) | |
| Constructs a new digital net formed by the first \(n = 2^k\) points of a Sobol' sequence, with \(w\) output digits, in dim in dimensions. | |
| SobolSequence (int n, int dim) | |
| Constructs a Sobol point set with at least n points and w=31 output digits, in dimension dim. | |
| SobolSequence (String filename, int k, int w, int dim) | |
| Constructs a new digital net using the direction numbers provided in file filename. | |
| String | toString () |
| Formats a string that contains information on this digital net. | |
| void | extendSequence (int k) |
| Increases the number of points to \(n = 2^k\) from now on. | |
| Public Member Functions inherited from umontreal.ssj.hups.DigitalSequenceBase2 | |
| DigitalNetBase2 | toNet () |
| Transforms this digital sequence into a digital net without changing the coordinates of the points. | |
| DigitalNetBase2 | toNetShiftCj () |
| Transforms this digital sequence into a digital net by adding one dimension and shifting all coordinates by one position. | |
| 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. | |
| PointSetIterator | iteratorShiftNoGray () |
| This iterator shifts all coordinates of each point one position to the right and sets the first coordinate of point \(i\) to. | |
| Public Member Functions inherited from umontreal.ssj.hups.DigitalNetBase2 | |
| double | getCoordinate (int i, int j) |
| Returns \(u_{i',j}\), the coordinate \(j\) of point \(i'\), where \(i'\) is the Gray code for \(i\). | |
| 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). | |
| PointSetIterator | iterator () |
| Returns a DigitalNetBase2Iterator which enumerates the points using a Gray code. | |
| PointSetIterator | iteratorNoGray () |
| This iterator does not use the Gray code. | |
| void | addRandomShift (int d1, int d2, RandomStream stream) |
| Generates a random digital shift for coordinates \(j\) from d1 to d2-1, using 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 digital random shift, if any. | |
| void | leftMatrixScramble (int r, RandomStream stream) |
| This is a version of LMS in which each column of the lower-triangular scrambling matrix is represented as an integer less than 2^w, just like for Cj. | |
| void | leftMatrixScramble (RandomStream stream) |
| By default, the matrices L_j have r = w rows. | |
| void | iBinomialMatrixScramble (RandomStream stream) |
| Similar to leftMatrixScramble, except that all entries on any given diagonal or subdiagonal of any given \(\mathbf{M}_j\) are identical. | |
| void | stripedMatrixScramble (RandomStream stream) |
| Applies the striped matrix scramble proposed by Owen. | |
| 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. | |
| void | nestedUniformScramble (RandomStream stream, double[][] output) |
| Same as nestedUniformScramble(stream, output, 0) . | |
| void | nestedUniformScramble (RandomStream stream, double[][] output, int numBits) |
| Applies Owen's nested uniform scrambling to the digital net and returns the scrambled points in the two-dimensional array output. | |
| void | nestedUniformScramble (RandomStream stream, int[][] output, int numBits) |
| Same as nestedUniformScramble(RandomStream,double[][],int), but it returns the points as integers from 0 to 2^outDigits - 1, instead of doubles. | |
| void | leftMatrixScrambleDiag (RandomStream stream) |
| Similar to leftMatrixScramble except that all the off-diagonal elements of the \(\mathbf{M}_j\) are 0. | |
| 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 [58] . | |
| void | leftMatrixScrambleFaurePermutDiag (RandomStream stream, int sb) |
| Similar to leftMatrixScrambleFaurePermut except that all off-diagonal elements are 0. | |
| 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 | iBinomialMatrixScrambleFaurePermut (RandomStream stream, int sb) |
| Similar to iBinomialMatrixScramble except that the diagonal elements of each matrix \(\mathbf{M}_j\) are chosen as in leftMatrixScrambleFaurePermut. | |
| void | iBinomialMatrixScrambleFaurePermutDiag (RandomStream stream, int sb) |
| Similar to iBinomialMatrixScrambleFaurePermut except that all the off-diagonal elements are 0. | |
| 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 | 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. | |
| void | unrandomize () |
| Restores the original generator matrices and removes the random shift. | |
| void | resetGenMatrices () |
| Restores genMat to the original generator matrices. | |
| void | eraseOriginalGenMatrices () |
| Erases the original generator matrices and replaces them by the current ones. | |
| int[][][] | genMatricesToBitByBitFormat () |
| Returns the generator matrices as a 3-dimensional array of shape dim x numRows x numCols integers, one integer for each bit. | |
| void | genMatricesFromBitByBitFormat (int[][][] matrices) |
| Reverse of the previous function. | |
| void | printGeneratorMatrices (int s) |
| Prints the generating matrices bit by bit for dimensions 1 to \(s\). | |
| void | printGenMatrices (int s) |
| Prints the generating matrices in the standard format, one integer per column, for dimensions 1 to \(s\). | |
| void | printOriginalMatrices (int s) |
| Prints the generating matrices in the standard format, one integer per column, for dimensions 1 to \(s\). | |
| int[] | getGenMatrices () |
| Returns a copy of the generator matrices for dimensions 1 to \(s\). | |
| void | outputInterlace (int[][] points, double[][] interlacedPoints) |
| Interlaces the points from a digital net. | |
| DigitalNetBase2 | matrixInterlace () |
| Interlaces the matrices from a digital net. | |
| Public Member Functions inherited from umontreal.ssj.hups.DigitalNet | |
| DigitalNet () | |
| Empty constructor. | |
| int | getInterlacing () |
| Returns the interlacing factor. | |
| void | setInterlacing (int interlacing) |
| Sets the interlacing factor. | |
| void | resetGeneratorMatrices () |
| Restores the original generator matrices. | |
| void | eraseOriginalGeneratorMatrices () |
| Erases the original generator matrices and replaces them by the current ones. | |
| Public Member Functions inherited from umontreal.ssj.hups.PointSet | |
| int | getDimension () |
| Returns the dimension (number of available coordinates) of the points. | |
| int | getNumPoints () |
| Returns the number of points. | |
| void | randomize (PointSetRandomization rand) |
| Randomizes this point set using the given rand. | |
| void | addRandomShift (int d1, int d2) |
| Refreshes the random shift (generates new uniform values for the random shift coordinates) for coordinates d1 to d2-1, using the saved shiftStream. | |
| void | addRandomShift () |
Same as addRandomShift(0, dim), where dim is the dimension of the point set. | |
| 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. | |
| 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. | |
| 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. | |
| String | formatPoints (PointSetIterator iter, int n, int d) |
Same as invoking formatPoints(n, d), but prints the points by calling iter repeatedly. | |
| String | formatPointsBase (int b) |
Similar to formatPoints(), but the points coordinates are printed in base \(b\). | |
| String | formatPointsBase (int n, int d, int b) |
Similar to formatPoints(n, d), but the points coordinates are printed in base \(b\). | |
| String | formatPointsBase (PointSetIterator iter, int b) |
Similar to formatPoints(iter), but the points coordinates are printed in base. | |
| 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\). | |
| String | formatPointsNumbered () |
Same as invoking formatPointsNumbered(n, d) with \(n\) and \(d\) equal to the number of points and the dimension, respectively. | |
| String | formatPointsNumbered (int n, int d) |
Same as invoking formatPoints(n,d), except that the points are numbered. | |
Static Protected Attributes | |
| static final int | MAXDIM = 360 |
| Maximal dimension for the primitive polynomials stored in this file. | |
| static final int | MAXDEGREE = 18 |
| Maximal degree of the primitive polynomials that are stored. | |
| static final int[] | poly |
| Ordered list of the first MAXDIM = 360 primitive polynomials. | |
| static final int | minit [][] |
| The default direction numbers, taken from Lemieux et al (2004). | |
| Static Protected Attributes inherited from umontreal.ssj.hups.PointSet | |
| static final int | MAXBITS = 31 |
| Since Java has no unsigned type, the 32nd bit cannot be used efficiently, so we have only 31 bits. | |
Additional Inherited Members | |
| Static Public Member Functions inherited from umontreal.ssj.hups.PointSet | |
| static int | getMaxBits () |
| Returns the maximum number of usable bits. | |
| Protected Attributes inherited from umontreal.ssj.hups.PointSet | |
| double | EpsilonHalf = 1.0 / Num.TWOEXP[55] |
| To avoid 0 for nextCoordinate when random shifting, we add this to each coordinate. | |
| int | dim = 0 |
| Dimension of the points. | |
| int | numPoints = 0 |
| Number of points. | |
| int | dimShift = 0 |
| Current dimension of the shift. | |
| int | capacityShift = 0 |
| Number of array elements in the shift vector, always >= dimShift. | |
| double[] | shift |
| This is the shift vector as a double[] array, which contains the current random shift in case we apply a random shift modulo 1. | |
| RandomStream | shiftStream |
| Stream used to generate the random shifts. | |
Detailed Description
This class implements digital nets and digital sequences in base 2 formed by the first \(n = 2^k\) points of a Sobol’ sequence [213], [rSOB76b].
Values of \(n\) up to \(2^{30}\) are allowed.
In Sobol’s proposal, the generator matrices \(\mathbf{C}_j\) are upper triangular matrices defined by a set of direction numbers
\[ v_{j,c} = m_{j,c} 2^{-c} = \sum_{l=1}^c v_{j,c,l} 2^{-l}, \]
where each \(m_{j,c}\) is an odd integer smaller than \(2^c\), for
\(c=1,…,k\) and \(j=0,…,s-1\). The digit \(v_{j,c,l}\) is the element \((l,c)\) of \(\mathbf{C}_j\), so \(v_{j,c}\) represents column \(c\) of \(\mathbf{C}_j\). One can also write
\[ m_{j,c} = \sum_{l=1}^c v_{j,c,l} 2^{c-l}, \]
so column \(c\) of \(\mathbf{C}_j\) contains the \(c\) digits of the binary expansion of \(m_{j,c}\), from the most to the least significant, followed by \(w-c\) zeros, where \(w\) is the number of output digits. Since each \(m_{j,c}\) is odd, the first \(k\) rows of each \(\mathbf{C}_j\) form a non-singular upper triangular matrix whose diagonal elements are all ones. The first one, \(\mathbf{C}_0\), is the identity matrix, with \(w-k\) rows of zeros at the bottom.
For each dimension \(j\), the integers \(m_{j,c}\) are defined by selecting a primitive polynomial over \(\mathbb F_2\) of degree \(c_j\),
\[ f_j(z) = z^{c_j} + a_{j,1}z^{c_j-1} + \cdots+ a_{j,c_j}, \]
and the first \(c_j\) integers \(m_{j,0},…,m_{j,c_j-1}\). Then the following integers \(m_{j,c_j}, m_{j, c_j+1}, …\) are determined by the recurrence
\[ m_{j,c} = 2 a_{j,1} m_{j,c-1} \oplus\cdots\oplus2^{c_j-1} a_{j,c_j-1}m_{j,c-c_j+1} \oplus2^{c_j} m_{j,c-c_j}\oplus m_{j,c-c_j} \]
for \(c\ge c_j\), or equivalently,
\[ v_{j,c,l} = a_{j,1} v_{j,c-1,l} \oplus\cdots\oplus a_{j,c_j-1} v_{j,c-c_j+1,l} \oplus v_{j,c-c_j,l}\oplus v_{j,c-c_j,l+c_j} \]
for \(l\ge0\), where \(\oplus\) means bitwise exclusive or (i.e., bitwise addition modulo 2). Sobol’ has shown [213] that with this construction, if the primitive polynomials \(f_j(z)\) are all distinct, one obtains a \((t,s)\)-sequence whose \(t\)-value does not exceed \(c_0 + \cdots+ c_{s-1} + 1 - s\). He then suggested to list the set of all primitive polynomials over \(\mathbb F_2\) by increasing order of degree, starting with \(f_0(z) \equiv1\) (whose corresponding matrix \(\mathbf{C}_0\) is the identity), and take \(f_j(z)\) as the \((j+1)\)th polynomial in the list, for \(j\ge0\).
This list of primitive polynomials, as well as default choices
for the direction numbers, are stored in precomputed tables.
The ordered list of primitive polynomials is the same as
in @cite iLEM04a; and was taken from Florent Chabaud’s web
site, at [http://fchabaud.free.fr/](http://fchabaud.free.fr/).
Each polynomial
\(f_j(z)\) is stored in the form of the integer \(2^{c_j} + a_{j,1}2^{c_j-1} + \cdots+ a_{j,c_j}\), whose binary representation gives the polynomial coefficients.
For the set of direction numbers, there are several possibilities based on different selection criteria. The original values proposed by Sobol’ and implemented in the code of Bratley and Fox [23] for \(j\le40\) were selected in terms of his properties \(A\) and \(A’\), which are equivalent to \(s\)-distribution with one and two bits of accuracy, respectively. The default direction numbers used in the present class have been taken from [158]. For \(j\le40\), they are the same as in [23]. Other direction numbers can be used by invoking SobolSequence(String,int,int,int) with the name of a file that contains the parameters. Several files of parameters for Sobol sequences are given on the web site of Frances Kuo. Good parameters can also be found by the LatNet Builder software available here
Definition at line 111 of file SobolSequence.java.
Constructor & Destructor Documentation
◆ SobolSequence() [1/3]
| umontreal.ssj.hups.SobolSequence.SobolSequence | ( | int | k, |
| int | w, | ||
| int | dim ) |
Constructs a new digital net formed by the first \(n = 2^k\) points of a Sobol' sequence, with \(w\) output digits, in dim in dimensions.
The predefined generating matrices \(\mathbf{C}_j\) are \(w\times k\), but only their first r = k rows are nonzero. Restrictions: \(0\le k\le30\), \(k\le w\) and dim \( \le360\). To use other direction numbers or to create points in higher dimensions, one should use SobolSequence(String,int,int,int) instead of this constructor.
- Parameters
-
k there will be 2^k points r number of rows of the generator matrices. w number of output digits after a random digital shift dim dimension of the point set
Definition at line 140 of file SobolSequence.java.
◆ SobolSequence() [2/3]
| umontreal.ssj.hups.SobolSequence.SobolSequence | ( | int | n, |
| int | dim ) |
Constructs a Sobol point set with at least n points and w=31 output digits, in dimension dim.
Equivalent to SobolSequence (k, 31, dim) with \(k = \lceil\log_2 n\rceil\).
- Parameters
-
dim dimension of the point set n minimal number of points
Definition at line 170 of file SobolSequence.java.
◆ SobolSequence() [3/3]
| umontreal.ssj.hups.SobolSequence.SobolSequence | ( | String | filename, |
| int | k, | ||
| int | w, | ||
| int | dim ) |
Constructs a new digital net using the direction numbers provided in file filename.
The net has \(n = 2^k\) points, \(w\) output digits and dimension dim. The file can be either on the user’s host, or somewhere on the Internet: in that case, the full url address must be given using either the http or ftp protocol. For example:
net = new SobolSequence( "http://web.maths.unsw.edu.au/~fkuo/sobol/joe-kuo-6.16900", k, w, dim);
The file must have the following format (the first line is treated as a comment by the program and discarded):
| dim | \(s\) | \(a\) | \(m_i\) |
| 2 | 1 | 0 | 1 |
| 3 | 2 | 1 | 1 3 |
| 4 | 3 | 1 | 1 3 1 |
| 5 | 3 | 2 | 1 1 1 |
| 6 | 4 | 1 | 1 1 3 3 |
| 7 | 4 | 4 | 1 3 5 13 |
| \(\vdots\) | \(\vdots\) |
where dim is the dimension, \(s\) the degree of the polynomial, the binary representation of \(a\) gives the inner coefficients of the polynomial (the first and the last coefficients are always 1), and
\(m_i\) are the direction numbers. Thus if \(a = (a_1 a_2 …a_{s-1})_2\) for a given \(s\), then the polynomial is \(x^s + a_1x^{s-1} + a_2x^{s-2} + \cdots+ a_{s-1} x + 1\), so \(a_0 = a_s = 1\). For example, if \(s=4\) and \(a=4 = 100_2\), then the polynomial is \(x^4 + x^3 +1\).
Several files of parameters for Sobol sequences in this format are given at http://web.maths.unsw.edu.au/~fkuo/sobol/ in up to 21201 dimensions. The different files give parameters that were selected using different criteria. To avoid waiting for a file to download every time a SobolSequence object is created, one should download the desired files and store them locally for faster access by invoking this constructor with the name of a local file.
- Parameters
-
k number of points is \(2^k\) w number of output digits dim dimension of the point set filename file containing the direction numbers
Definition at line 271 of file SobolSequence.java.
Member Function Documentation
◆ extendSequence()
| void umontreal.ssj.hups.SobolSequence.extendSequence | ( | int | k | ) |
Increases the number of points to \(n = 2^k\) from now on.
- Parameters
-
k there will be 2^k points
Reimplemented from umontreal.ssj.hups.DigitalSequenceBase2.
Definition at line 368 of file SobolSequence.java.
◆ toString()
| String umontreal.ssj.hups.SobolSequence.toString | ( | ) |
Formats a string that contains information on this digital net.
- Returns
- string representation of basic information on this digital net
Reimplemented from umontreal.ssj.hups.DigitalNetBase2.
Definition at line 362 of file SobolSequence.java.
Member Data Documentation
◆ MAXDEGREE
|
staticprotected |
Maximal degree of the primitive polynomials that are stored.
Definition at line 121 of file SobolSequence.java.
◆ MAXDIM
|
staticprotected |
Maximal dimension for the primitive polynomials stored in this file.
Definition at line 116 of file SobolSequence.java.
◆ minit
|
staticprotected |
The default direction numbers, taken from Lemieux et al (2004).
For \(j > 0\) and \(c < c_j\), minit[j-1][c] contains the integer \(m_{j,c}\). The values for \(j=0\) are not stored, since \(\mathbf{C}_0\) is the identity matrix.
*** Pierre: I think thse should also be put in a file, not in the code.
Definition at line 481 of file SobolSequence.java.
◆ poly
|
staticprotected |
Ordered list of the first MAXDIM = 360 primitive polynomials.
Definition at line 450 of file SobolSequence.java.
The documentation for this class was generated from the following file:
- src/main/java/umontreal/ssj/hups/SobolSequence.java
