This class provides the basic structures for storing and manipulating linear digital nets in base \(b\), for an arbitrary base \(b\ge2\). More...
This class provides the basic structures for storing and manipulating linear digital nets in base \(b\), for an arbitrary base \(b\ge2\).
We recall that a net contains \(n = b^k\) points in \(s\) dimensions, where the \(i\)th point \(\mathbf{u}_i\), for \(i=0,…,b^k-1\), is defined as follows:
\begin{align*} i & = \sum_{\ell=0}^{k-1} a_{i,\ell} b^{\ell}, \\ \begin{pmatrix} u_{i,j,1} \\ u_{i,j,2} \\ \vdots \end{pmatrix} & = \mathbf{C}_j \begin{pmatrix} a_{i,0} \\ a_{i,1} \\ \vdots \\ a_{i,k-1} \end{pmatrix} , \\ u_{i,j} & = \sum_{\ell=1}^{\infty}u_{i,j,\ell} b^{-\ell}, \\ \mathbf{u}_i & = (u_{i,0},\dots,u_{i,s-1}). \end{align*}
In our implementation, the matrices \(\mathbf{C}_j\) are \(r\times k\), so the expansion of \(u_{i,j}\) is truncated to its first \(r\) terms. The points are stored implicitly by storing the generator matrices \(\mathbf{C}_j\) in a large two-dimensional array of integers, with \(srk\) elements. For general \(b\), the element \((l,c)\) of \(\mathbf{C}_j\) (counting elements from 0) is stored at position \([jk+c][l]\) in this array.
To enumerate the points, one should avoid using the method getCoordinate(i, j) for arbitrary values of i and j, because this is much slower than using a PointSetIterator to access successive coordinates. By default, the iterator enumerates the points \(\mathbf{u}_i\) using a Gray code technique as proposed in [8], [230], and also described in [69], [88]). With this technique, the \(b\)-ary representation of \(i\), \(\mathbf{a}_i = (a_{i,0}, …, a_{i,k-1})\), is replaced in Equation (digital-Cj) by a Gray code representation of \(i\), \(\mathbf{g}_i = (g_{i,0}, …, g_{i,k-1})\). The Gray code \(\mathbf{g}_i\) used here is defined by \(g_{i,k-1} = a_{i,k-1}\) and \(g_{i,\ell} = (a_{i,\ell} - a_{i,\ell+1}) \bmod b\) for \(\ell= 0,…,k-2\). It has the property that \(\mathbf{g}_i = (g_{i,0}, …, g_{i,k-1})\) and \(\mathbf{g}_{i+1} = (g_{i+1,0}, …, g_{i+1,k-1})\) differ only in the position of the smallest index \(\ell\) such that \(a_{i,\ell} < b - 1\), and we have \(g_{i+1,\ell} = (g_{i,\ell}+1) \bmod 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 \(\mathbf{u}_i\) are enumerated, but the first \(b^m\) points remain the same for every integer \(m\). The \(i\)th 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 \(\mathbf{a}_{i’}\) is given by the Gray code \(\mathbf{g}_i\). To enumerate all the points successively, we never need to compute the Gray codes explicitly. It suffices to know the position \(\ell\) of the Gray code digit that changes at each step, and this can be found quickly from the \(b\)-ary representation \(\mathbf{a}_i\). The digits of each coordinate \(j\) of the current point can be updated by adding column \(\ell\) of the generator matrix \(\mathbf{C}_j\) to the old digits, modulo \(b\).
Digital nets can be randomized in various ways [178], [59], [126], [195]. 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 \(u_{i,j,\ell}\) in ( digital-uij ) by \((u_{i,j,\ell} + d_{j,\ell}) \bmod b\), where the \(d_{j,\ell}\)’s are i.i.d. uniform over \(\{0,\dots,b-1\}\). This is equivalent to applying a single random shift to all the points in a formal series representation of their coordinates [126], [161]. In practice, the digital shift is truncated to \(w\) digits, for some integer \(w\ge r\). Applying a digital shift does not change the equidistribution and \((t,m,s)\)-net properties of a point set [88], [124], [161]. Moreover, with the random shift, each point has the uniform distribution 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 [178], [59], [88], [195], which multiply the matrices \(\mathbf{C}_j\) by a random invertible matrix \(\mathbf{M}_j\), modulo \(b\). There are several variants, depending on how \(\mathbf{M}_j\) is generated, and on whether \(\mathbf{C}_j\) is multiplied on the left or on the right. In our implementation, the linear matrix scrambles are incorporated directly into the matrices \(\mathbf{C}_j\) (as in [88]), 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 \(\mathbf{C}_j\)’s. A copy of the original \(\mathbf{C}_j\)’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 could be useful if one wishes to apply two or more linear matrix scrambles on top of each other and not retain the original matrices.
With the linear matrix scrambles alone, the randomized points do not have the uniform distribution over the unit cube. For this reason, they are usually combined with a random digital shift; this combination is called an affine matrix scramble [195]. These two randomizations are applied via separate methods. The linear matrix scrambles are incorporated into the matrices \(\mathbf{C}_j\) whereas the digital random shift is stored and applied separately, independently of the other scrambles.
Applying a digital shift or a linear matrix scramble to a digital net invalidates all current iterators for the current 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 or randomization that affects the DigitalNet object, the iterators must be reinitialized to the initial point by invoking PointSetIterator.resetCurPointIndex or re-instantiated by the iterator method (this is not done automatically).
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4