Generating parallel quasirandom sequences via randomization

• Published in: Journal of parallel and distributed computing 2007-07, Vol.67 (7), p.876-881
• Main Authors: Chi, Hongmei, Jones, Edward L.
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Exact sciences and technology; Parallel computing; Quasi-Monte Carlo; Randomization; Scrambling; Software
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2007.04.004

Quasi-Monte Carlo (QMC) methods are now widely used in scientific computation, especially in estimating integrals over multidimensional domains. One advantage of QMC is that it is easy to parallelize applications, and so the success of any parallel QMC application depends crucially on the quality of parallel quasirandom sequences used. Much of the recent work dealing with parallel QMC methods has been aimed at splitting a single quasirandom sequence into many subsequences. In contrast with this perspective to concentrate on breaking one sequence up, this paper proposes an alternative approach to generating parallel sequences for QMC. This method generates parallel sequences of quasirandom numbers via scrambling. The exact meaning of scrambling depends on the type of parallel quasirandom numbers. In general, we seek to randomize the generator matrix for each quasirandom number generator. Specifically, this paper will discuss how to parallelize the Halton sequence via scrambling. The proposed scheme for generating parallel random number streams is especially good for heterogeneous and unreliable computing environments.