Pseudorandom vector generation by the inversive method

ABSTRACT

Pseudorandom vectors are of importance for parallelized simulation methods. In this article we carry out a detailed analysis of the inversive method for the generation of uniform pseudorandom vectors. This method can be viewed as an analog of the inversive congruential method for pseudorandom number generation. We study, in particular, the periodicity properties and the behavior under the serial test for sequences of pseudorandom vectors generated by the inversive method.

REFERENCES

• 1: L. Afflerbach , H. Grothe, The lattice structure of pseudo-random vectors generated by matrix generators, Journal of Computational and Applied Mathematics, v.23 n.1, p.127-131, July 1988 [doi>10.1016/0377-0427(88)90338-X]
• 2: 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]
• 3: V. C. Bhavsar , J. R. Isaac, Design and analysis of parallel Monte Carlo algorithms, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.73-95, January 2, 1987 [doi>10.1137/0908014]
• 4: CHOU, W.-S. 1993. On inversive maximal period polynomials over finite fields. Preprint, Austrian Academy of Sciences, Vienna.
• 5: W. F. Eddy, Random number generators for parallel processors, Journal of Computational and Applied Mathematics, v.31 n.1, p.63-71, July 1990 [doi>10.1016/0377-0427(90)90336-X]
• 6: EICHENAUER, J. AND LEHN, J. 1986. A non-linear congruential pseudo random number generator. Stat. Papers 27, 315-326.
• 7: Jürgen Eichenauer-Herrmann, Improved lower bounds for the discrepancy of inversive congruential pseudorandom numbers, Mathematics of Computation, v.62 n.206, p.783-786, April 1994 [doi>10.2307/2153538]
• 8: EICHENAUER-HERRMANN, J. 1992. Inversive congruential pseudorandom numbers: A tutorial. Int. Stat. Rev. 60, 167 176.
• 9: FLAHIVE, M. AND NIEDERREITER, H. 1992. On inversive congruential generators for pseudorandom numbers. In Finite Fields, Coding Theory, and Advances tn Communications and Computing, G. L. Mullen and P. J.-S. Shine, Eds. Dekker, New York, 75 80.
• 10: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 11: KuPE~S, L. AND N~EDERREITER, H. 1974. Uniform Dtstributzon of Sequences. Wiley, New York.
• 12: Pierre L'Ecuyer, Random numbers for simulation, Communications of the ACM, v.33 n.10, p.85-97, Oct. 1990 [doi>10.1145/84537.84555]
• 13: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 14: LIDL, R. AND NIEDERREITER, H. 1983. Finite Fields. Addison-Wesley, Reading, Mass (Now distributed by Cambridge University Press.)
• 15: MORENO, C. J. AND MORENO, O. 1991. Exponential sums and Goppa codes: I. Prec. Am. Math. Soc. 111,523-531.
• 16: NmDERREITE~, H. 1993. Factorization of polynomials and some linear-algebra problems over finite fields. Lin. Alg. Appl. 192, 301 328.
• 17: NIEDERREITER, H. 1992a. Nonlinear methods for pseudorandom number and vector generation. In Simulation and Optimization, G. Pfiug and U. Dieter, Eds. Lecture Notes in Economics and Mathematical Systems, vol. 374. Springer, Berhn, 145 153.
• 18: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 19: NIEDERREITER, H. 1991. Finite fields and their applications. In Contributions to General Algebra 7 (Vienna, 1990). Teubner, Stuttgart, 251 264.
• 20: H. Niederreiter, Statistical independence properties of pseudorandom vectors produced by matrix generators, Journal of Computational and Applied Mathematics, v.31 n.1, p.139-151, July 1990 [doi>10.1016/0377-0427(90)90345-Z]
• 21: NIEDERREITER, H. 1990b. Lower bounds for the discrepancy ofinversive congruentml pseudorandom numbers. Math Comput. 55, 277 287.
• 22: NIEDERREITER, H. 1978. Quasi-Monte Carlo methods and pseudo-random numbers Bull. Am. Math. Soc. 84, 957-1041.
• 23: NIEDERREITER, H. 1977. Pseudo-random numbers and optimal coefficients. Adv. Math. 26, 99-181.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
inversive method, parallelized simulation methods, pseudorandom vectors