Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Pseudorandom vector generation by the multiple-recursive matrix method

Author: Harald Niederreiter
Journal: Math. Comp. 64 (1995), 279-294
MSC: Primary 65C10; Secondary 11K45
MathSciNet review: 1265018
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Pseudorandom vectors are of importance for parallelized simulation methods. In this paper we carry out an in-depth analysis of the multiple-recursive matrix method for the generation of uniform pseudorandom vectors which was introduced in an earlier paper of the author. We study, in particular, the periodicity properties, the lattice structure, and the behavior under the serial test for sequences of pseudorandom vectors generated by this method.

References [Enhancements On Off] (What's this?)

  • [1] Lothar Afflerbach and Holger Grothe, The lattice structure of pseudo-random vectors generated by matrix generators, J. Comput. Appl. Math. 23 (1988), no. 1, 127–131. MR 952072, 10.1016/0377-0427(88)90338-X
  • [2] Stuart L. Anderson, Random number generators on vector supercomputers and other advanced architectures, SIAM Rev. 32 (1990), no. 2, 221–251. MR 1056053, 10.1137/1032044
  • [3] V. C. Bhavsar and J. R. Isaac, Design and analysis of parallel Monte Carlo algorithms, SIAM J. Sci. Statist. Comput. 8 (1987), no. 1, S73–S95. Parallel processing for scientific computing (Norfolk, Va., 1985). MR 873952, 10.1137/0908014
  • [4] William F. Eddy, Random number generators for parallel processors, J. Comput. Appl. Math. 31 (1990), no. 1, 63–71. Random numbers and simulation (Lambrecht, 1988). MR 1068149, 10.1016/0377-0427(90)90336-X
  • [5] Jürgen Eichenauer and Jürgen Lehn, A nonlinear congruential pseudorandom number generator, Statist. Hefte 27 (1986), no. 4, 315–326. MR 877295
  • [6] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
  • [7] P. L'Ecuyer, Random numbers for simulation, Comm. ACM 33 (1990), no. 10, 85-97.
  • [8] Pierre L’Ecuyer, Uniform random number generation, Ann. Oper. Res. 53 (1994), 77–120. Simulation and modeling. MR 1310607, 10.1007/BF02136827
  • [9] Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394
  • [10] M. Matsumoto and Y. Kurita, Twisted GFSR generators, ACM Trans. Modeling Comput. Simulation 2 (1992), 179-194.
  • [11] Harald Niederreiter, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), no. 2, 99–181. MR 0476679
  • [12] Harald Niederreiter, The serial test for pseudorandom numbers generated by the linear congruential method, Numer. Math. 46 (1985), no. 1, 51–68. MR 777824, 10.1007/BF01400255
  • [13] H. Niederreiter, Statistical independence properties of pseudorandom vectors produced by matrix generators, J. Comput. Appl. Math. 31 (1990), no. 1, 139–151. Random numbers and simulation (Lambrecht, 1988). MR 1068157, 10.1016/0377-0427(90)90345-Z
  • [14] Harald Niederreiter, Finite fields and their applications, Contributions to general algebra, 7 (Vienna, 1990) Hölder-Pichler-Tempsky, Vienna, 1991, pp. 251–264. MR 1143089
  • [15] -, Nonlinear methods for pseudorandom number and vector generation, Simulation and Optimization (G. Pflug and U. Dieter, eds.), Lecture Notes in Econom. Math. Systems, vol. 374, Springer, Berlin, 1992, pp. 145-153.
  • [16] Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997
  • [17] Harald Niederreiter, Factorization of polynomials and some linear-algebra problems over finite fields, Linear Algebra Appl. 192 (1993), 301–328. Computational linear algebra in algebraic and related problems (Essen, 1992). MR 1236747, 10.1016/0024-3795(93)90247-L
  • [18] -, Pseudorandom vector generation by the inversive method, ACM Trans. Modeling Comput. Simulation (to appear).
  • [19] Harald Niederreiter, The multiple-recursive matrix method for pseudorandom number generation, Finite Fields Appl. 1 (1995), no. 1, 3–30. MR 1334623, 10.1006/ffta.1995.1002
  • [20] Brian D. Ripley, Stochastic simulation, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Inc., New York, 1987. MR 875224

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C10, 11K45

Retrieve articles in all journals with MSC: 65C10, 11K45

Additional Information

Article copyright: © Copyright 1995 American Mathematical Society