Stephen Joe
Abstract
An algorithm to generate Sobol' sequences to approximate integrals in up to 40 dimensions has been previously given by Bratley and Fox in Algorithm 659. Here, we provide more primitive polynomials and "direction numbers" so as to allow the generation of Sobol' sequences to approximate integrals in up to 1111 dimensions. The direction numbers given generate Sobol' sequences that satisfy Sobol's so-called Property A.
- Acworth, P. A., Broadie, M., and Glasserman, P. 1998. A comparison of some Monte Carlo and quasi-Monte Carlo techniques for option pricing. In Monte Carlo and Quasi-Monte Carlo Methods 1996, H. Niederreiter, P. Hellekalek, G. Larcher, and P. Zinterhof, Eds. Lecture Notes in Statistics, vol. 127. Springer, New York, 1--18.]]Google Scholar
- Antonov, I. A. and Saleev, V. M. 1979. An economic method of computing LPτ-sequences. Zh. v&ymacr;chisl. Mat. mat. Fiz. 19, 243--245. English translation: U.S.S.R. Comput. Maths. Math. Phys. 19, 252--256.]]Google Scholar
- Bratley, P. and Fox, B. L. 1988. Algorithm 659: Implementing Sobol's quasirandom sequence generator. ACM Trans. Math. Softw. 14, 88--100.]] Google ScholarDigital Library
- Cheng, J. and Druzdzel, M. J. 2000. Computational investigation of low-discrepancy sequences in simulation algorithms for Bayesian networks. In Proceedings of the 16th Annual Conference on Uncertainty in Artificial Intelligence, C. Boutilier and M. Goldszmidt, Eds. Morgan-Kaufmann, San Francisco, Calif., 72--81.]] Google ScholarDigital Library
- Fox, B. L. 1986. Algorithm 647: Implementation and relative efficiency of quasirandom sequence generators. ACM Trans. Math. Softw. 12, 362--376.]] Google ScholarDigital Library
- Morokoff, W. J. and Caflisch, R. E. 1994. Quasi-random sequences and their discrepancies. SIAM J. Sci. Comput. 15, 1251--1279.]] Google ScholarDigital Library
- Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo methods. SIAM, Philadelphia, Pa.]] Google ScholarDigital Library
- Paskov, S. H. and Traub, J. F. 1995. Faster valuation of financial derivatives. J. Portf. Manage. 22, 113--120.]]Google ScholarCross Ref
- Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 1992. Numerical Recipes in Fortran 77: The Art of Scientific Computing, 2nd ed. Cambridge University Press, Cambridge, U.K.]] Google ScholarDigital Library
- Sloan, I. H., Kuo, F. Y., and Joe, S. 2002. Constructing randomly shifted lattice rules in weighted Sobolev spaces. SIAM J. Numer. Anal. 40, 1650--1665.]] Google ScholarDigital Library
- Sobol', I. M. 1967. On the distribution of points in a cube and the approximate evaluation of integrals. Zh. v&ymacr;chisl. Mat. mat. Fiz. 7, 784--802. English translation: U.S.S.R. Comput. Maths. Math. Phys. 7, 86--112.]]Google Scholar
- Sobol', I. M. 1976. Uniformly distributed sequences with an additional uniform property. Zh. v&ymacr;chisl. Mat. mat. Fiz. 16, 1332--1337. English translation: U.S.S.R. Comput. Maths. Math. Phys. 16, 236--242.]]Google Scholar
- Sobol', I. M. and Levitan, Y. L. 1976. The production of points uniformly distributed in a multidimensional cube. Tech. Rep. 40, Institute of Applied Mathematics, USSR Academy of Sciences. (In Russian).]]Google Scholar
- Wang, X. and Fang, K.-T. 2002. The effective dimensions and quasi-Monte Carlo integration. J. Complexity, submitted for publication.]] Google ScholarDigital Library
Index Terms
- Remark on algorithm 659: Implementing Sobol's quasirandom sequence generator
Recommendations
Implementation and tests of low-discrepancy sequences
Low-discrepancy sequences are used for numerical integration, in simulation, and in related applications. Techniques for producing such sequences have been proposed by, among others, Halton, Sobol´, Faure, and Niederreiter. Niederreiter's sequences have ...
Computational investigations of low-discrepancy sequences
The Halton, Sobol, and Faure sequences and the Braaten-Weller construction of the generalized Halton sequence are studied in order to assess their applicability for the quasi Monte Carlo integration with large number of variates. A modification of the ...
Programs to generate Niederreiter's low-discrepancy sequences
This note points out programs to implement Niederreiter's low-discrepancy sequences.
Comments