Abstract
Much of the recent work on parallelizing quasi-Monte Carlo methods has been aimed at splitting a quasirandom sequence into many subsequences which are then used independently on the various parallel processes. This method works well for the parallelization of pseudorandom numbers, but due to the nature of quality in quasirandom numbers, this technique has many drawbacks. In contrast, this paper proposes an alternative approach for generating parallel quasirandom sequences via scrambling. The exact meaning of the digit scrambling we use depends on the mathematical details of the quasirandom number sequence’s method of generation. The Faure sequence is scramble by modifying the generator matrices in the definition. Thus, we not only obtain the expected near-perfect speedup of the naturally parallel Monte Carlo methods, but the errors in the parallel computation is even smaller than if the computation were done with the same quantity of quasirandom numbers using the original Faure sequence.
Chapter PDF
Similar content being viewed by others
References
Beerli, P., Chi, H.: Quasi-markov chain Monte Carlo to improve inference of population genetic parameters. Mathematics and Computers in Simulation, in press (2007)
Bromley, B.C.: Quasirandom number generators for parallel Monte Carlo algorithms. Journal of Parallel and Distributed Computing 38(1), 101–104 (1996)
Chi, H., Mascagni, M., Warnock, T.: On the optimal Halton sequences. Mathematics and Computers in Simulation 70(1), 9–21 (2005)
Faure, H.: Discrepancy of sequences associated with a number system (in dimension s). Acta. Arith. 41(4), 337–351 (1982)
Faure, H.: Variations on (0,s)-sequences. Journal of Complexity 17(4), 741–753 (2001)
Fox, B.: Implementation and relative efficiency of quasirandom sequence generators. ACM Trans. on Mathematical Software 12, 362–376 (1986)
Jank, W.: Efficient simulated maximum likelihood with an application to online retailing. Statistics and Computing 16, 111–124 (2006)
Kocis, L., Whiten, W.: Computational investigations of low discrepancy sequences. ACM Trans. Mathematical software 23, 266–294 (1997)
Li, Y., Mascagni, M.: Analysis of large-scale grid-based Monte Carlo applications. International Journal of High Performance Computing Applications 17(4), 369–382 (2003)
Liu, K., Hickernell, F.J.: A scalable low discrepancy point generator for parallel computing. In: Cao, J., Yang, L.T., Guo, M., Lau, F. (eds.) ISPA 2004. LNCS, vol. 3358, pp. 257–262. Springer, Heidelberg (2004)
Loh, W.L.: On the asymptotic distribution of scrambled net quadrature. Annals of Statistics 31, 1282–1324 (2003)
Mascagni, M., Chi, H.: Parallel linear congruential generators with Sophie-Germain moduli. Parallel Computing 30, 1217–1231 (2004)
Mascagni, M., Srinivasan, A.: Algorithm 806: SPRNG: A scalable library for pseudorandom number generation. ACM Transactions on Mathematical Software 26, 436–461 (2000)
Niederreiter, H.: Random number generation and quasi-Monte Carlo methods. SIAM, Philadephia (1992)
Owen, A.B.: Randomly permuted (t,m,s)-nets and (t,s)-sequences. In: Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing. Lecture Notes in Statistics, vol. 106, pp. 299–317 (1995)
Owen, A.B., Tribble, S.: A quasi-Monte Carlo metroplis algorithm. Proceedings of the National Academy of Sciences of the United States of America 102, 8844–8849 (2005)
Papageorgiou, A., Traub, J.: Beating Monte Carlo. RISK 9, 63–65 (1997)
Schmid, W., Uhl, A.: Techniques for parallel quasi-Monte Carlo integration with digital sequences and associated problems. Math. Comput. Simulat. 55(1-3), 249–257 (2001)
Soboĺ, I.M.: Uniformly distributed sequences with additional uniformity properties. USSR Comput. Math. and Math. Phy. 16, 236–242 (1976)
Tezuka, S.: Uniform Random Numbers, Theory and Practice. Kluwer Academic Publishers, Dordrecht (1995)
Tezuka, S., Faure, H.: I-binomial scrambling of digital nets and sequences. Journal of Complexity 19(6), 744–757 (2003)
Tezuka, S., Tokuyama, T.: A note on polynomial arithmetic analogue of Halton sequences. ACM Trans. on Modelling and Computer Simulation 4, 279–284 (1994)
Wang, X., Fang, K.T.: The effective dimension and quasi-monte carlo. Journal of Complexity 19(2), 101–124 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Chi, H., Mascagni, M. (2007). Efficient Generation of Parallel Quasirandom Faure Sequences Via Scrambling. In: Shi, Y., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds) Computational Science – ICCS 2007. ICCS 2007. Lecture Notes in Computer Science, vol 4487. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72584-8_96
Download citation
DOI: https://doi.org/10.1007/978-3-540-72584-8_96
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72583-1
Online ISBN: 978-3-540-72584-8
eBook Packages: Computer ScienceComputer Science (R0)