An obvious way to get parallel streams of PRNs is to partition a sequence of a given pseudorandom number generator into suitable subsequences. This can be achieved in different ways.
In Subsection , we study the well known ``leap-frog'' technique where the original sequence of a generator is split into lagged subsequences with a given lag . Whereas a single stream of a LCG performs well in practice, due to good spectral test results, the quality of lagged subsequences of such a stream may be worsen considerably. Hence whenever lagged subsequences occur in a particular simulation problem these sequences have to be tested as well.
In  we showed how to analyze correlations within and between lagged subsequences with arbitrary step sizes generated from LCGs with power-of-two- and prime moduli. In Subsection we recall basic concepts from  and apply them to several examples of LCGs.
By varying the initial seed one easily may partition a sequence of a LCG into consecutive blocks of a given length. An extensive discussion of this method for LCGs with respect to parallelization was given by DeMatteis and Pagnutti  (see also [38,40,41,42,43,44,53]). It turns out that only reduced fractions of sequences produced by LCGs can safely be used because of the well known long-range correlations which may cause high correlations between parallel streams. Critical lengths of consecutive blocks for several LCGs are given e.g. for RANF [38,40,42], L'Ecuyer LCG 3 , MINSTD , Super-Duper and RANDU . Using the spectral test it is possible to exhibit these long-range correlations in a stronger way. Whereas the latter authors studied correlations between pairs of processors only, the spectral test offers an easy tool to analyze correlations between an arbitrary number of parallel streams, see Subsection .
Sometimes it is recommended, to use separate generators to produce parallel streams of random numbers e.g. see . In Subsection we give a simple example of three LCGs with perfect spectral test results but strong correlations within the parallel streams obtained from these generators.
Our subsequence analyses of LCGs use classical notions from linear random number generation. A more general analysis of lagged subsequences with arbitrary lacunary indices from multiple recursive generators has been discussed and performed in [136,148].
With the ``leap-frog'' technique [16,27,54,132,134]
of a LCG is partitioned into lagged subsequences of the form
Consider a mixed linear congruential generator with
maximal period . For this
generator, the subsequence () is also produced by (see also
Even if one chooses subsequences with maximal period , these sequences can be of inferior quality. This can be easily shown by the spectral test. The table below gives some examples. G_k denotes the LCG which generates a full-period subsequence of generator G. Further results can be found in [62,63].
Note that FISH15_23, FISH7_105 exhibit normalized spectral test results worse than RANDU. The zoom into the 3-dimensional unit cube above stems from FISH15_23. The second graphics shows the 15 hyperplanes that cover all three-dimensional overlapping tuples generated by FISH7_105. A parallel application using LCG.1 is given in .
If a subsequence-LCG does not have full period, the underlying lattice structure obviously can be of reduced quality as well. In the graphics below we demonstrate this behavior with some zooms into the unit square which contain all overlapping vectors generated by the by the LCGs: MINSTD_77, SIMSCRIPT_78 and RANF_36 . Compare the zooms in the Sections , and .
But how to assess non-full period subsequences with the spectral test? As an example, we consider ``the reminder of the good old days, the early 1950s'', the LCG with multiplier (BCSLIB, URN12, CDC Computers, SIMULA)7, which already was analyzed by Coveyou and MacPherson  with the spectral test. In particular we analyze certain non-full period subsequences of which, especially for , is studied in different parallel settings (including the leap-frog method) in .
Quote[16, p. 451]: This 'leapfrog' algorithm was subjected to an analysis of correlation, exactly as was done for the Lehmer tree algorithm. The choices , , and were again made and 50000 numbers were generated in each parallel sequence for analysis by linear regression. From 8 to 512 parallel processes were examined. No significant correlations were found between pairs of processes.
Let's make a more detailed study of these ``8 to 512 parallel processes''. In the subsections below we first recall some basic lattice theory of LCGs and then study the quality reduction of the lattice structure generated by lagged subsequences with step sizes , of . Note that this analysis applies to arbitrary linear congruential pseudorandom number generator with power-of-two moduli as well.
We now describe the lattice structure obtained by subsequences ()
with step sizes , . Recall the basic recursion of :
, , and w.l.o.g. .
From [201, Prop. 1] (see also [73, p. 599]) we get
Therefore, the spectral test of the -subsequences has to be calculated using the latter vector (with constant !).
Note that if one uses constant for the calculation, this would give the spectral test for the union of all subsequence-grids. This is not the appropriate way to asses the subsequence structure. For example, the GEN-subsequence with step size yields the weak spectral test whereas for the union of the subsequence-grids .
We applied the normalized spectral test , , to -subsequences with step sizes , . As can be seen from the tables below, with increasing , the quality of the subsequence-lattices strongly decreases. The tables report the results for with moduli , , 35, 48. Perhaps there are no ``correlations'' between pairs of parallel streams, as stated above, but the quality of each stream is very poor for .
The same analysis as for was made for RANF (Sect. ) as well . In the case of RANF, step sizes , are of special interest, since such step sizes are implemented on CRAY systems (e.g. see the Cray Math Library Reference Manual SR-2080). Similar as for the lagged subsequences with step sizes 64, 128, 256, 512 show poor spectral test results.
For large power-of-two step sizes we can
determine the spectral test for arbitrary multiplicative LCGs with
power-of-two moduli . Let ,
Therefore the order of
the multiplicative group equals
From () and () we obtain
Now let . Equation () yields , and therefore . Further we observe that for and thus for the latter powers . Similarly, for the same range of , we have and therefore for .
Again consider . The table below verifies the calculations above. It exhibits the values and the normalized spectral tests for and step sizes , . Note that for we obtain . The spectral tests for and can also be verified theoretically in the same way as above (in this case we observe that ).
In Entacher  we showed how to analyze correlations within and between lagged subsequences with arbitrary step sizes generated from LCGs with power-of-two- and prime moduli. The main results of the latter paper are the following:
Consider the full period standard cases of LCGs: (i) is prime, is a primitive root modulo , , and , (ii) is a power of 2, , and c is odd, and finally (iii) and as in (ii) but and is odd [8,73,130,184,201].
In sharp contrast to LCGs with power-of-two moduli, lagged subsequences from prime LCGs (i) exhibit no pure lattice structure in general. As examples, consider ,78,0,1) and ,114,0,1). The graphics on the left side in the figures below show the lattice structure of all overlapping vectors in dimension generated from (upper graphics) and , whereas the remaining plots show the structures obtained by the subsequences () with step sizes and . The spectral tests (as described below) are given in the figures as well.
Using the spectral test for the assessment of correlations within lagged subsequences () with step size generated from prime LCGs, one has to apply the lattice in the calculation of the test. But in the non-full-period case (), this strategy yields the assessment of the union of all overlapping vectors generated by each subsequence () with . As you may imagine from the figures above, additional correlation analysis should be performed for each single subsequence. Nevertheless, the latter lattice can be applied for finding (bad) subsequences and for a correlation analysis of consecutive blocks (), see Section below.
In order to analyze correlations between lagged subsequences of prime LCGs one has to assess the same set of vectors , as in Remark . Similar as for overlapping vectors of lagged subsequences from prime LCGs, these vectors exhibit no pure lattice structure in general. Therefore the spectral test is not the obvious measure to assess such correlations, exept of an analysis of full-period subsequences.
As an example we use GEN with modulus , and consider consecutive blocks of length , . The graphics below shows vectors , , , for block lengths , , respectively. Below the plots, the spectral tests and the estimates for the number of hyperplanes are given as well. Whereas the correlations between pairs of consecutive streams with decreasing block length rapidly become better, the spectral tests in dimension remain stable.
These graphics exhibit strong ``long-range'' correlations between consecutive streams with large block size. Such long-range correlations between pairs of consecutive blocks have already been studied by DeMatteis and Pagnutti et al. [39,41,38,42,43,44,59]. Using the spectral test to assess such correlations was already suggested by Durst  and related concepts can be found in [40,195] 8. Similar as DeMatteis et. al. the latter authors applied their correlation analysis only in dimension two for computational and mathematical reasons.
In this section we will update the concepts mentioned above, i.e. we use the spectral test to extend the analysis of correlations between consecutive blocks of random numbers to higher dimensions . The following table shows a normalized spectral test analysis of consecutive blocks obtained from GEN. The table contains results of for block lengths , and dimensions . From the spectral test results we observe that, no practically relevant consecutive blocks (with power-of-two block lengths) from GEN and related generators should be used in parallel.
Note that in contrast to the spectral tests in Subsection , the tables below exhibit spectral tests of the union of all grids produced from overlapping vectors of subsequences with step size .
Using only odd block lengths (hence the block length does not divide the period of the generator which also implies that , has full period) provides a simple way against correlations between consecutive blocks obtained from power-of-two LCGs. But previously testing is recommended in this case as well. The table below shows normalized spectral tests , , using for block lengths , . Similarly, as for the results below there are no conspicuous correlations for .
For prime LCGs there are long-range correlations as well. As an example we consider MINSTD. Typical behavior of prime LCGs in long-range correlation analyses with the spectral test is shown in the table below9. We derived the normalized spectral test , using MINSTD and lattice , , with block lengths , for . Note that equals the period of MINSTD. The table reports those results where at least one value , , turns out to be lower than . Column gives the prime factors of since from the results below one may assume that there is a strong impact between the prime factors of the period and those of critical distances (for more details see the theoretical verification below).
As a first consequence these results require to perform any long-range correlation analysis or calculations of critical distances [38,42,43,59] also in higher dimensions . Consider for example the case , which means that we partition the full period of into three consecutive blocks of length , each of which is used as a single stream in parallel. The spectral-test shows that there are strong correlations within all three streams, whereas pairs of these streams are not correlated due to the large value of . Further illustration is provided by the measure which in case equals and . Hence, overlapping three dimensional vectors lie in at most two hyper-planes whereas two dimensional vectors lie within a fine lattice structure, due to the large number of hyper-planes estimated in dimension two.
For block lengths with small divisors of the period , we easily can verify the behavior of certain spectral test results in the table above. In this case the order of in the multiplicative group equals . Hence for prime numbers we get , and therefore the weak spectral test . Now consider non-prime divisors . For example let . Thus we get . Let . From we obtain . For dimension we use and , which yield . Similar calculations yield the entries of the following table which are valid for arbitrary primitive roots modulo , and hence for all full period multiplicative LCGs with prime modulus . The table below exhibits the values for .
For the situation slightly changes. In this case, the (bad) spectral test values depend on the explicit multiplier . For this multiplier we get and therefore , which yields the bad spectral tests in dimensions . Note that for an holds for all primitive roots . Hence, if equals a multiple of 31 such as we also obtain bad results.
From arbitrary separate generators, parallel streams of random numbers can be generated as well. This strategy is sometimes recommended in the literature e.g. see , or supported by parallel random number libraries . In this section we want to demonstrate the danger of this strategy. As a simple example consider the following three LCGs: Let , , and , and denote the multiplicative LCG with modulus , seed and multiplier by . These multipliers are proposed in [171, Table 7] for use in parallel environments. was also proposed by Fishman, see Section . The normalized spectral tests of all three LCGs in the latter dimensions are given in the table below.
There are no conspicuous correlations between parallel streams generated from these LCGs as we may assume from the scatter plots of vectors and given in the following graphics.
But if we change multiplier and generate the same plots as before, we easily can exhibit strong correlations between parallel streams from these LCGs, see the graphics below. Note that the new multiplier yields perfect spectral test results and as well.