Design, Search and Implementation of Improved Large Order Multiple Recursive Generators and Matrix Congruential Generators

Large order, maximum period multiple recursive generators (MRGs) with few nonzero terms (e.g., DX-k-s generators) have become popular in the area of computer simulation. They are efficient, portable, have a long period, and have the nice property of high-dimensional equi-distribution. The latter two properties become more advantageous as k increases. The performance on the spectral test, a theoretical test that provides some measure of uniformity in dimensions beyond the MRG\u27s order k, could be improved by choosing multipliers that yield a better spectral test value. We propose a new method to compute the spectral test which is simple, intuitive, and efficient for some special classes of large order MRGs. Using this procedure, we list \u27\u27better\u27\u27 FMRG-k and DX-k-s generators with respect to performance on the spectral test. Even so, MRGs with few nonzero terms do not perform as well with respect to the spectral test as MRGs with many nonzero terms. However, MRGs with many nonzero terms can be inefficient or lack a feasible parallelization method, i.e., a method of producing substreams of (pseudo) random numbers that appear independent. To implement these MRGs efficiently and in parallel, we can use an equivalent recursion from another type of generator, the matrix congruential generator (MCG), a k-dimensional generalization of a first order linear recursion where the multipliers are embedded in a k by k matrix. When MRGs are used to construct MCGs and the recursion of the MCG is implemented k at a time for a k-dimensional vector sequence, then the MCG mimics k copies of a MRG in parallel with different starting seeds. Therefore, we propose a method for efficiently finding MRGs with many nonzero terms from an MRG with few nonzero terms and then give an efficient and parallel MCG implementation of these MRGs with many nonzero terms. This method works best for moderate order k. For large order MRGs with many nonzero terms, we propose a special class called DW-k. This special class has a characteristic polynomial that yields many nonzero terms and corresponds to an efficient and parallel MCG implementation