Description
Low Discrepancy Sequences in Scilab
Scilab already provide several random number generators of high quality via the grand function. But, in the context of Monte-Carlo simulations, uniform random numbers may provide a slow convergence of the algorithm. For example in the case of numerical integration, it is known that a low discrepancy sequence can improve convergence speed of the algorithm.
This is why we have developped a module which provide low discrepancy sequences.
The current prototype has the following features :
- manage arbitrary number of dimensions,
- skips a given number of elements in the sequence,
- leaps (i.e. ignores) a given number of elements from call to call.
This module currently provides the following functions:
- lowdisc_cget : Returns the value associated with the given key for the given object.
- lowdisc_configure : Update one option of the current object and returns an updated object.
- lowdisc_destroy : Destroy the current object and returns an updated object.
- lowdisc_display : Prints the current sequence.
- lowdisc_new : Creates and returns a new sequence.
- lowdisc_next : Returns the next vector in the sequence.
- lowdisc_reset : Reset the random number generator.
- lowdisc_startup : Startup a random number object.
- lowdisc_terms : Returns several terms of the sequence.
This component currently provides the following sequences:
- "slow" sequences based on macros : vandercorput, halton, faure, reversehalton, sobol, niederreiter-base-2,
- "fast" sequences based on C source code : reversehaltonf, niederreiter-base-2f, sobolf, fauref, haltonf.
The current toolbox contains help pages and unit tests. Several algorithms provided in this tool are ported from the work by John Burkardt [11].
Ideas
In this section, we provide a project related to this topic. We especially detail the expected outputs of this project. We also analyse the tools which might be required. In all cases, a small scientific report at the end of the project will be welcome. We emphasize the benefits of the project for the student. We also detail the software management of the produced source code.
In both cases, the first step of the project will require to update the existing help pages. This will allow the student to get the knowledge of the current system.
Provide a C++ implementation of the sequences.
The "fast" sequences provided in C are not in C++, i.e. are not object-oriented. This has many drawbacks. The first one is that it creates an unconsistency between the API, which is object-oriented, and the underlying code, which is not. Therefore, no more than one fast Sobol sequence can be managed. Another consequence is that parallel simulations will not be manageable easily. The goal of this project is to provide a C++ implementation of these sequences. This will require to design a low discrepancy class and to re-design the existing algorithms. Once done, a consistent set of gateways must be created. That may be based on a token system similar to what has been used in the NISP module [12]. The final step will be to connect the macro-based API to the object-oriented gateways (this is the easy step). At the end of the project, the student will master low discrepancy sequences, which are used in many practical situations in industrial context, finance, etc... The project requires programming skills. This project does not require to modify Scilab and this is why it will be managed via the Scilab forge. The main tool for this project is a C++ compiler.
Other projects related to the same issues are welcome, for example: add more sequences, add more scrambling algorithms, provide a Matlab-like interface.
Bibliography
- [1] Monte-Carlo methods in Financial Engineering, Paul Glasserman
- [2] J H Halton and G B Smith, Algorithm 247: Radical-Inverse Quasi-Random Point Sequence, Communications of the ACM, Volume 7, 1964, pages 701-702.
- [3] Reverse Halton, B. Vandewoestyne and R. Cools, Good permutations for deterministic scrambled Halton sequences in terms of L2-discrepancy, Computational and Applied Mathematics 189, 2006
- [4] Harald Niederreiter, Low-discrepancy and low-dispersion sequences, Journal of Number Theory, Volume 30, 1988, pages 51-70.
- [5] Halton, J. H. 1964. Algorithm 247: Radical-inverse quasi-random point sequence. Commun. ACM 7, 12 (Dec. 1964), 701-702
- [6] Fox, B. L. 1986. Algorithm 647: Implementation and Relative Efficiency of Quasirandom Sequence Generators. ACM Trans. Math. Softw. 12, 4 (Dec. 1986), 362-376.
- [7] Bratley, P. and Fox, B. L. 1988. Algorithm 659: Implementing Sobol's quasirandom sequence generator. ACM Trans. Math. Softw. 14, 1 (Mar. 1988), 88-100.
- [8] Bratley, P., Fox, B. L., and Niederreiter, H. 1994. Programs to generate Niederreiter's low-discrepancy sequences. ACM Trans. Math. Softw. 20, 4 (Dec. 1994), 494-495.
- [9] Hong, H. S. and Hickernell, F. J. 2003. Algorithm 823: Implementing scrambled digital sequences. ACM Trans. Math. Softw. 29, 2 (Jun. 2003), 95-109.
- [10] Discrepancy of sequences associated with a number system (in dimension one), Faure Henri, Bull. Soc. Math. France 109, no. 2, 143--182, 1981
[11] The Faure Quasirandom Sequence, John Burkardt, http://people.sc.fsu.edu/~burkardt/m_src/faure/faure.html
[12] Non Intrusive Spectral Projection, http://atoms.scilab.org/toolboxes/NISP/2.1