Abstract
Sobol sequence is the most widely used low discrepancy sequence for numerical solving of multiple integrals and other quasi-Monte Carlo computations. Owen first proposed scrambling of this sequence through permutation in a manner that maintained its low discrepancy. Scrambling is necessary not only for error analysis but for parallel implementations. Good scrambling is especially important for GRID applications. However, scrambling is often difficult to implement and time consuming. In this paper we propose fast generation of Sobol sequence with Owen scrambling, tuned to specific hardware. Numerical and timing results, demonstrating the advantages of our approach are presented and discussed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Atanassov, E.: A New Efficient Algorithm for Generating the Scrambled Sobol Sequence. In: Dimov, I.T., Lirkov, I., Margenov, S., Zlatev, Z. (eds.) NMA 2002. LNCS, vol. 2542, pp. 83–90. Springer, Heidelberg (2003)
Bromley, B.C.: Quasirandom Number Generation for Parallel Monte Carlo Algorithms. Journal of Parallel Distributed Computing 38(1), 101–104 (1996)
Caflisch, R.: Monte Carlo and quasi-Monte Carlo methods. Acta Numerica 7, 1–49 (1998)
Chi, H.: Scrambled Quasirandom Sequences and Their Applications, PhD dissertation, FSU (2004)
Chi, H., Jones, E.: Generating Parallel Quasirandom Sequences by using Randomization. Journal of Distributed and Parallel Computing 67(7), 876 (2007)
Chi, H., Mascagni, M.: Efficient Generation of Parallel Quasirandom Sequences via Scrambling. In: Shi, Y., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds.) ICCS 2007. LNCS, vol. 4487, pp. 723–730. Springer, Heidelberg (2007)
Cranley, R., Patterson, T.: Randomization of number theoretic methods for multiple integration. SIAM Journal of Numerical Analysis 13(6), 904–914 (1976)
Davis, P., Rabinowitz, P.: Methods of Numerical Integration. Academic Press, New York (1984)
Genz, A.: The numerical evaluation of multiple integrals on parallel computers. In: Keast, P., Fairweather, G. (eds.) Numerical Integration, pp. 219–230. D. Reidel, Dordrecht (1987)
Goeddeke, D., Strzodka, R., Turek, S.: Performance and accuracy of hardware-oriented native-, emulated- and mixed-precision solvers in FEM simulations. International Journal of Parallel, Emergent and Distributed Systems 22(4), 221–256 (2007)
Hong, H., Hickernell, F.: Algorithm 823: Implementing scrambled digital sequences. ACM Transactions on Mathematical Software 29(2), 95–109 (2003)
Joe, S., Kuo, F.: Remark on Algorithm 659: Implementing Sobol’s quasirandom sequence generator. ACM Transactions on Mathematical Software 29(1), 49–57 (2003)
Niederreiter, H.: Low-discrepancy and low-dispersion sequences. Journal of Number Theory 30(1), 51–70 (1988)
Niederreiter, H.: Random Number Generations and Quasi-Monte Carlo Methods. SIAM, Philadelphia (1992)
Owen, A.: 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.: Scrambled net variance for integrals of smooth functions. Annals of Statistics 25, 1541–1562 (1997)
Owen, A.: Scrambling Sobo’l and Niederreiter-Xing points. Journal of Complexity 14, 466–489 (1998)
Owen, A.: Variance with alternative scramblings of digital nets. ACM Transactions on Modeling and Computer Simulation 13(4), 363–378 (2003)
Sobol, I.M.: Uniformly distributed sequences with additional uniformity properties. USSR Comput. Math. and Math. Phy. 16, 236–242 (1976)
Radovic, I., Sobol, I.M., Tichy, R.: Quasi-Monte Carlo methods for numerical integration: Comparison of different low discrepancy sequences. Monte Carlo Methods and Appl. 2, 1–14 (1996)
Tezuka, S.: Quasi-Monte Carlo discrepancy between theory and practice. In: Fang, K.T., Hickernell, F., Niederreiter, H. (eds.) MC&QMC Methods, pp. 124–140. Springer, Berlin (2002)
Wang, X., Fang, K.: The effective dimension and quasi-Monte Carlo. Journal of Complexity 19(2), 101–124 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Atanassov, E., Karaivanova, A., Ivanovska, S. (2010). Tuning the Generation of Sobol Sequence with Owen Scrambling. In: Lirkov, I., Margenov, S., Waśniewski, J. (eds) Large-Scale Scientific Computing. LSSC 2009. Lecture Notes in Computer Science, vol 5910. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12535-5_54
Download citation
DOI: https://doi.org/10.1007/978-3-642-12535-5_54
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12534-8
Online ISBN: 978-3-642-12535-5
eBook Packages: Computer ScienceComputer Science (R0)