𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the structure of parallelized random number sources

✍ Scribed by Jun Makino


Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
686 KB
Volume
78
Category
Article
ISSN
0010-4655

No coin nor oath required. For personal study only.

✦ Synopsis


A set of numbers which constitutes a period in a pseudorandom sequence is equipartitioned into segments which are then arranged in rows or in columns to form a two-dimensional array. Such an array may be called a parallelized random number source, because its rows can be used as random number sequences which work independently of each other. For many parallelized Monte Carlo computations, it seems to be of essential importance that the parallelized source is sufficiently random in the column direction as well as in the row direction. Randomness of the original sequence, which is investigated by a series of theoretical and statistical tests, is reflected in the direction in which random numbers are arranged. Randomness in the orthogonal direction, however, can be either good or poor according to the way the source is parallelized. In this paper, structure of a parallelized source is discussed when it is viewed in the orthogonal direction. By number theoretic argument, some general conclusions are deduced which depend only on the period of the original sequence and the way the source is parallelized. These conclusions can be used to avoid bad parallelization in designing a parallelized source. Simple examples of such application are given for the congruential method and for the shift register method both of which are in use today on parallel computers.


πŸ“œ SIMILAR VOLUMES


On the independence number of random gra
✍ A.M. Frieze πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 239 KB

Let (Y(G~,~) denote the independence number of the random graph Gn,p. Let d = np. We show that if E > 0 is fixed then with probability going to 1 as n + m cu(G& -$t (log d -log log dlog 2 + 1) < 7 provided d, s d = o(n), where d, is some fixed constant.

Randomized On-line Scheduling of Paralle
✍ JiΕ™Δ±&amp;#x0301; Sgall πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 230 KB

We study randomized on-line scheduling on mesh machines. We show that for scheduling independent jobs randomized algorithms can achieve a significantly better performance than deterministic ones; on the other hand with dependencies randomization does not help.

On the chromatic number of a random 5-re
✍ J. DΓ­az; A. C. Kaporis; G. D. Kemkes; L. M. Kirousis; X. PΓ©rez; N. Wormald πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 275 KB πŸ‘ 1 views

## Abstract It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is as