Remark on algorithm 659: Implementing Sobol's quasirandom sequence generator

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.

REFERENCES

• 1: 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.
• 2: 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.
• 3: Paul Bratley , Bennett L. Fox, ALGORITHM 659: implementing Sobol's quasirandom sequence generator, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.88-100, March 1988 [doi>10.1145/42288.214372]
• 4: Jian Cheng , Marek J. Druzdzel, Computational Investigation of Low-Discrepancy Sequences in Simulation Algorithms for Bayesian Networks, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.72-81, June 30-July 03, 2000
• 5: Bennett L. Fox, Algorithm 647: Implementation and Relative Efficiency of Quasirandom Sequence Generators, ACM Transactions on Mathematical Software (TOMS), v.12 n.4, p.362-376, Dec. 1986 [doi>10.1145/22721.356187]
• 6: William J. Morokoff , Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM Journal on Scientific Computing, v.15 n.6, p.1251-1279, Nov. 1994 [doi>10.1137/0915077]
• 7: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 8: Paskov, S. H. and Traub, J. F. 1995. Faster valuation of financial derivatives. J. Portf. Manage. 22, 113--120.
• 9: 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.
• 10: I. H. Sloan , F. Y. Kuo , S. Joe, Constructing Randomly Shifted Lattice Rules in Weighted Sobolev Spaces, SIAM Journal on Numerical Analysis, v.40 n.5, p.1650-1665, 2002 [doi>10.1137/S0036142901393942]
• 11: 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.
• 12: 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.
• 13: 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).
• 14: Xiaoqun Wang , Kai-Tai Fang, The effective dimension and quasi-Monte Carlo integration, Journal of Complexity, v.19 n.2, p.101-124, April 2003 [doi>10.1016/S0885-064X(03)00003-7]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Multidimensional (multiple) quadrature

General Terms:
Algorithms

Keywords:
Low-discrepancy sequences, Sobol' sequences, primitive polynomials, quasirandom sequences