Parallel streams of linear random numbers in the spectral test

ABSTRACT

This paper reports analyses of subsequences of linear congruential pseudorandom numbers by means of the spectral test. Such subsequences occur in particular simulation setups or as methods to obtain parallel streams of pseudorandom numbers for parallel and distributed simulation. Especially in the latter case, two kinds of substreams are of special interest: lagged random numbers with step sizes k, and consecutive streams of random numbers of length l. We show how to analyze correlations within and between lagged subsequences with arbitrary step sizes k. Analyzing consecutive streams with the spectral test is related to the well-known long-range correlation analysis of linear congruential generators. Whereas the latter was carried out to show correlations between pairs of processors only, the spectral test provides a convenient method to study correlations between larger numbers of parallel streams as well.

REFERENCES

• 1: Stuart L. Anderson, Random number generations generators on Vector supercomputers and other advanced architectures, SIAM Review, v.32 n.2, p.221-251, June 1990 [doi>10.1137/1032044]
• 2: CEPERLEY, D., MASCAGNI, M., AND SRINIVASAN, A. 1997. SPRNG: Scalable parallel random number generators. University of Illinois at Urbana-Champaign, Champaign, IL. http:// www.ncsa.uiuc.edu/Apps/SPRNG/
• 3: R. R. Coveyou , R. D. Macpherson, Fourier Analysis of Uniform Random Number Generators, Journal of the ACM (JACM), v.14 n.1, p.100-119, Jan. 1967 [doi>10.1145/321371.321379]
• 4: A. De Matteis , J. Eichenauer-Herrmann , H. Grothe, Computation of critical distances within multiplicative congruential pseudorandom number sequences, Journal of Computational and Applied Mathematics, v.39 n.1, p.49-55, Feb. 28, 1992 [doi>10.1016/0377-0427(92)90221-I]
• 5: A. De Matteis , S. Pagnutti, Parallelization of random number generators and long-range correlations, Numerische Mathematik, v.53 n.5, p.595-608, August 1988 [doi>10.1007/BF01397554]
• 6: DEMATTEIS, A. AND PAGNUTTI, S. 1990. A class of parallel random number generators. Parallel Comput. 13, 193-198.
• 7: DEMATTEIS, A. AND PAGNUTTI, S. 1992. Critical distances in pseudorandom sequences generated with composite moduli. Int. J. Comput. Math. 43, 189-196.
• 8: A. De Matteis , S. Pagnutti, Controlling correlations in parallel Monte Carlo, Parallel Computing, v.21 n.1, p.73-84, Jan. 1995 [doi>10.1016/0167-8191(94)00073-J]
• 9: DIETER, U. 1975. How to calculate shortest vectors in a lattice. Math. Comput. 29, 131, 827-833.
• 10: M. J. Durst, Using linear congruential generators for parallel random number generation, Proceedings of the 21st conference on Winter simulation, p.462-466, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76798]
• 11: J. Eichenauer-Herrmann , Holger Grothe, A remark on long-range correlations in multiplicative congruential pseudo random number generators, Numerische Mathematik, v.56 n.6, p.609-611, Dec. 1989 [doi>10.1007/BF01396346]
• 12: EICHENAUER-HERRMANN, J., HERRMANN, E., AND WEGENKITTL, S. 1998. A survey of quadratic and inversive congruential pseudorandom numbers. In Lecture Notes in Statistics. Springer-Verlag, New York, NY, 66-97.
• 13: Karl Entacher, Bad subsequences of well-known linear congruential pseudorandom number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.61-70, Jan. 1998 [doi>10.1145/272991.273009]
• 14: ENTACHER, K. 1998. A collection of selected pseudorandom number generators with linear structures -- updated version. Tech. Rep.. Dept. of Mathematics, University of Salzburg, Austria. http://random.mat.sbg, ac. at/
• 15: K. Entacher , A. Uhl , S. Wegenkittl, Linear and inversive pseudorandom numbers for parallel and distributed simulation, Proceedings of the twelfth workshop on Parallel and distributed simulation, p.90-97, May 26-29, 1998, Banff, Alberta, Canada
• 16: FISHMAN, G. 1996. Monte Carlo: Concepts, algorithms, and applications. In Operations Research. Springer Series on Operations Research, vol. 1. Springer-Verlag, New York, NY.
• 17: Peter Hellekalek, Inversive pseudorandom number generators: concepts, results and links, Proceedings of the 27th conference on Winter simulation, p.255-262, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224612]
• 18: HELLEKALEK, P. 1998a. On correlation analysis of pseudorandom numbers. In Lecture Notes in Statistics. Springer-Verlag, New York, NY, 251-265.
• 19: HELLEKALEK, P. 1998b. On the assessment of random and quasi-random point sets. In Random and Quasi-Random Point Sets. P. Hellekalek and G. Larcher, Eds. Lecture Notes in Statistics. Springer-Verlag, New York, NY.
• 20: HELLEKALEK, P., ENTACHER, K., LEEB, H., LENDL, O., AND WEGENKITTL, S. 1995. The pLab www-server. Available at: http://random.mat.sbg.ac.at+. Also accessible via ftp. University of Salzburg, Austria.
• 21: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 22: Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
• 23: L'ECUYER, P. 1997. Bad lattice structures for vectors of non-successive values produced by some linear recurrences. INFORMS J. Comput. 9, 57-60.
• 24: L'ECUYER, P. 1998. Random number generation. In Handbook of Simulation, J. Banks, Ed. John Wiley & Sons, Inc., New York, NY.
• 25: Pierre L'Ecuyer, Tables of linear congruential generators of different sizes and good lattice structure, Mathematics of Computation, v.68 n.225, p.249-260, Jan. 1999 [doi>10.1090/S0025-5718-99-00996-5]
• 26: Pierre L'Ecuyer , Terry H. Andres, A random number generator based on the combination of four LCGs, Mathematics and Computers in Simulation, v.44 n.1, p.99-107, May 1997 [doi>10.1016/S0378-4754(97)00052-9]
• 27: L'ECUYER, P. AND COUTURE, R. 1997. An implementation of the lattice and spectral tests for multiple recursive linear random number generators. INFORMS J. Comput. 9, 2, 206-217.
• 28: Michael Mascagni, Parallel linear congruential generators with prime moduli, Parallel Computing, v.24 n.5-6, p.923-936, June 1998 [doi>10.1016/S0167-8191(98)00010-6]
• 29: MASUDA, N. AND ZIMMERMANN, F. 1996. PRNGlib: A parallel random number generator library. Tech. Rep.. http://www.cscs.ch/Official/Publications.html.
• 30: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 31: NIEDERREITER, H. 1995. New developments in uniform pseudorandom number and vector generation. In Monte Carlo and Quasi Monte Carlo Methods in Scientific Computing, H. Niederreiter and P. J.-S. Shiue, Eds. Springer-Verlag, New York, NY.
• 32: Ora E. Percus , Malvin H. Kalos, Random number generators for MIMD parallel processors, Journal of Parallel and Distributed Computing, v.6 n.3, p.477-497, June 1989 [doi>10.1016/0743-7315(89)90002-6]
• 33: RIPLEY, B. 1983. The lattice structure of pseudo-random number generators. Phil. Trans. Roy. Soc. London Ser. A 389, 197-204.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms

Keywords:
lattice structure, leap-frog technique, linear congruential generator, long-range correlations, parallel random numbers, random number generation, spectral test, stochastic simulation