Algorithm 659: Implementing Sobol's quasirandom sequence generator

ABSTRACT

We compare empirically accuracy and speed of low-discrepancy sequence generators of Sobol' and Faure. These generators are useful for multidimensional integration and global optimization. We discuss our implementation of the Sobol' generator.

REFERENCES

• 1: ANTONOV, I. A., AND SALEEV, V.M. An economic method of computing LP~-sequences. USSR Comput. Math. Math. Phys. 19 (1979), 252-256.
• 2: DAVIS, P. J., AND RABINOWITZ, P. Methods o{ Numerical Integration. Academic Press, New York, 1983.
• 3: FAURE, H. Discr~pance de suites associ~es ~ un syst~me de numeration (en dimension s). Acta Arithmetica XLI (1982), 337-351.
• 4: 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]
• 5: HALTON, J.H. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2 (1960), 84-90.
• 6: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 7: PETERSON, W. W., AND WELDON, E.J. Error-Correcting Codes. 2nd ed. MIT Press, Cambridge, Mass., 1972.
• 8: NIEDERREITER, H. Point sets and sequences with small discrepancy. Monatsh. Math. (to appear).
• 9: P. K. Sarkar , M. A. Prasad, A comparative study of Pseudo and Quasi random sequences for the solution intergral equations, Journal of Computational Physics, v.68 n.1, p.66-88, January 2, 1987 [doi>10.1016/0021-9991(87)90045-3]
• 10: SOBOL', I. M. On the distribution of points in a cube and the approximate evaluation of integrals. USSR Comput. Math. Math. Phys. 7 (1967), 86-112.
• 11: SOBOL', I.M. Uniformly distributed sequences with an additional uniform property. USSR Comput. Math. Math. Phys. 16 (1976), 236-242.
• 12: SOBOL', I.M. On the systematic search in a hypercube. SIAM J. Numer. Anal. 16 (1979), 790-793.
• 13: SOBOL', I. M. Points which uniformly fill a multidimensional cube. Math. Cybern. 2 (1985) Znanie, Moscow (in Russian).
• 14: SOBOL', I. M., AND LEVITAN, Yu.L. The production of points uniformly distributed in a multidimensional cube. Preprint 40, Institute of Applied Mathematics, USSR Academy of Sciences, 1976 (in Russian).
• 15: AMERICAN NATIONAL STANDARDS INSTITUTES. American National Standard Programming Language FORTRAN. Standard X3.9-1978, American National Standards Institute, New York, 1978.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing; Efficiency

General Terms:
Algorithms, Measurement, Performance

Keywords:
computational complexity, discrepancy, generators, global optimization, multidimensional integration, quasirandom sequences