An overview of configurable options of the generators.
In this section, we present the options supported by the various
sequences.
These are the keys of the lowdisc_configure
function.
We set a "O" in the table when the low discrepancy sequence is sensitive to the
corresponding option.
Option | Halton | Sobol | Faure | Niederreiter |
"-dimension" | O | O | O | O |
"-skip" | O | O | O | O |
"-leap" | O | O | O | O |
"-verbose" | O | O | O | O |
"-primeslist" | O | O | ||
"-base" | O | |||
"-scrambling" | O | O | ||
"-seeds" | O |
For the Halton sequence, the skip
and
leap
option are fast, that is, large
values of the skip
or leap
parameter do not reduce the performance.
This fast algorithm is based on a compiled C source code. The implementation is a modification of the C source code by John Burkardt.
Reference : http://people.sc.fsu.edu/~jburkardt/cpp_src/halton/halton.html, The Halton Quasirandom Sequence, John Burkardt
For the Faure sequence, the skip
and
leap
option is fast, that is, large
values of the skip
or leap
parameter do not reduce the performance.
This fast algorithm is based on a compiled C source code. The implementation is a modification of the C source code by John Burkardt.
Reference : http://www.netlib.org/toms/647, "Algorithm 647: Implementation and Relative Efficiency of Quasirandom Sequence Generators", Bennett Fox, ACM Transactions on Mathematical Software (TOMS), Volume 12 Issue 4, Dec. 1986, Pages 362-376
Reference : http://people.sc.fsu.edu/~jburkardt/cpp_src/faure/faure.html, The Faure Quasirandom Sequence, John Burkardt
The Reverse Halton sequence is just a specialized scrambling of the Halton sequence.
Each dimension is associated with a given permutation, which changes the order of the points in the sequence. The scrambling is based on the permutation:
sigma(digit)=0, if digit==0, sigma(digit)=base-digit, otherwise,
where base is the base (a prime number) associated with the dimension. This produces the following permutations:
0 1 0 2 1 0 5 4 3 2 1 0 7 6 5 4 3 2 1 etc...
This fast algorithm is based on the same C++ source code as the Halton sequence.
Reference : "Good permutations for deterministic scrambled Halton sequences in terms of L2-discrepancy", B. Vandewoestyne and R. Cools, Journal of Computational and Applied Mathematics, Volume 189 Issue 1-2, May, 2006, Pages 341-361
The unscrambled routine adapts the ideas of Antonov and Saleev,
which make use of a Gray code representation to construct the
elements of the sequence recursively.
For the Sobol sequence, the skip
and
leap
options are slow, that is, large
values of the skip
or leap
parameter lead to increased CPU time.
This is because generating the new vector implies to update iteratively
the lastq vector.
This fast algorithm is based on a compiled C source code. The unscrambled implementation is a modification of the C source code by John Burkardt. The scrambled implementation is a C++ port of the original Fortran source code.
Reference for Unscrambled Sobol : http://www.netlib.org/toms/647 "Algorithm 647: Implementation and Relative Efficiency of Quasirandom Sequence Generators", Bennett Fox, ACM Transactions on Mathematical Software, Volume 12 Issue 4, Dec. 1986, Pages 362-376
Reference for Scrambled Sobol : http://www.netlib.org/toms/823 "Algorithm 823: Implementing scrambled digital sequences", Hee Sun Hong, Fred J. Hickernell, ACM, Transactions on mathematical software, Volume 29, NO. 2, June, 2003, P. 95--109.
For the Niederreiter sequence, the skip
and
leap
option is slow, that is, large
values of the skip
or leap
parameter leads to increased CPU time.
This is because generating the new vector implies to update iteratively
the nextq vector.
The library generates two temporary files gfarit and gfplys when the sequence is started up.
This fast algorithm is based on a compiled C source code. The C port has been done by John Burkardt in 2005-2009. The library has been updated to present a uniform API.
Reference: http://www.netlib.org/toms/738, "Algorithm 738: Programs to generate Niederreiter's low-discrepancy sequences" (1994), Paul Bratley, Bennett Fox, Harald Niederreiter.
Reference : http://people.sc.fsu.edu/~jburkardt/cpp_src/niederreiter/niederreiter.html, The Niederreiter Quasirandom Sequence, John Burkardt