Shifted Sobol points and multigrid Monte Carlo simulation

Cover Page

Cite item

Full Text

Abstract

Multidimensional integrals arise in many problems of physics. For example, moments of the distribution function in the problems of transport of various particles (photons, neutrons, etc.) are 6-dimensional integrals. When calculating the coefficients of electrical conductivity and thermal conductivity, scattering integrals arise, the dimension of which is equal to 12. There are also problems with a significantly large number of variables. The Monte Carlo method is the most effective method for calculating integrals of such a high multiplicity. However, the efficiency of this method strongly depends on the choice of a sequence that simulates a set of random numbers. A large number of pseudo-random number generators are described in the literature. Their quality is checked using a battery of formal tests. However, the simplest visual analysis shows that passing such tests does not guarantee good uniformity of these sequences. The magic Sobol points are the most effective for calculating multidimensional integrals. In this paper, an improvement of these sequences is proposed: the shifted magic Sobol points that provide better uniformity of points distribution in a multidimensional cube. This significantly increases the cubature accuracy. A significant difficulty of the Monte Carlo method is a posteriori confirmation of the actual accuracy. In this paper, we propose a multigrid algorithm that allows one to find the grid value of the integral simultaneously with a statistically reliable accuracy estimate. Previously, such estimates were unknown. Calculations of representative test integrals with a high actual dimension up to 16 are carried out. The multidimensional Weierstrass function, which has no derivative at any point, is chosen as the integrand function. These calculations convincingly show the advantages of the proposed methods.

Full Text

Introduction Integrals of multivariate functions occur in many areas of physics. Here are some examples. The transfer of neutrons, photons and other particles in © Belov A.A., Tintul M.A., 2021 This work is licensed under a Creative Commons Attribution 4.0 International License http://creativecommons.org/licenses/by/4.0/ the medium is described by the equation for the distribution function; this function depends on three coordinates of the medium and three components of the particle velocity vector, that is, the number of variables is six. To determine the coefficients of thermal conductivity or electrical conductivity of a medium, it is necessary to calculate the collision integrals; they include components of the velocity vectors before the moment of collision and after the moment of collision. The total number of variables in such an integral is twelve. Problems also arise with a significantly larger number of variables. In the simplest formulation, the calculation of the integral in the unit

×

About the authors

Aleksandr A. Belov

M.V. Lomonosov Moscow State University; Peoples’ Friendship University of Russia (RUDN University)

Author for correspondence.
Email: aa.belov@physics.msu.ru
ORCID iD: 0000-0002-0918-9263

Candidate of Physical and Mathematical Sciences, Assistant professor of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University); Researcher of Faculty of Physics, M.V. Lomonosov Moscow State University

1, bld. 2, Leninskie Gory, Moscow, 119991, Russian Federation; 6, Miklukho-Maklaya St., Moscow, 117198, Russian Federation

Maxim A. Tintul

M.V. Lomonosov Moscow State University

Email: maksim.tintul@mail.ru
ORCID iD: 0000-0002-5466-1221

Master’s degree student of Faculty of Physics

1, bld. 2, Leninskie Gory, Moscow, 119991, Russian Federation

References

  1. I. M. Sobol, Numerical Monte-Carlo methods [Chislennyye metody MonteKarlo]. Moscow: Nauka, 1973, In Russian.
  2. D. E. Knuth, The art of computer programming, 3rd ed. Reading, Massachusetts: Addison-Wesley, 1997, vol. 2.
  3. G. S. Fishman, Monte Carlo: concepts, algorithms and applications. Berlin: Springer, 1996. doi: 10.1007/978-1-4757-2553-7.
  4. M. Matsumoto and T. Nishimura, “Mersenne twister: a 623dimensionally equidistributed uniform pseudo-random number generator,” ACM Transactions on Modeling and Computer Simulation (TOMACS), vol. 8, no. 1, pp. 3-30, 1998. doi: 10.1145/272991.272995.
  5. T. Nishimura, “Tables of 64-bit Mersenne twisters,” ACM Transactions on Modeling and Computer Simulation, vol. 10, no. 4, pp. 348-357, 2000. doi: 10.1145/369534.369540.
  6. “Mersenne Twister Home Page.” (2021), [Online]. Available: http:// www.math.sci.hiroshima-u.ac.jp/m-mat/MT/emt.html.
  7. S. K. Park and K. W. Miller, “Random number generators: good ones are hard to find,” Communications of the ACM, vol. 31, no. 10, pp. 1192-1201, 1998. doi: 10.1145/63039.63042.
  8. M. Mascagni and A. Srinivasan, “Parameterizing parallel multiplicative Lagged-Fibonacci generators,” Parallel Computing, vol. 30, pp. 899-916, 2004. doi: 10.1016/j.parco.2004.06.001.
  9. P. L’Ecuyer, “Good parameter sets for combined multiple recursive random number generators,” Operations Research, vol. 47, no. 1, pp. 159-164, 1999. doi: 10.1287/opre.47.1.159.
  10. J. K. Salmon, M. A. Moraes, R. O. Dror, and D. E. Shaw, “Parallel random numbers: as easy as 1, 2, 3,” 2011 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp. 1-12, 2011. doi: 10.1145/2063384.2063405.
  11. G. Marsaglia and W. W. Tsang, “The ziggurat method for generating random variables,” Journal of Statistical Software, vol. 5, pp. 1-7, 2000. doi: 10.18637/jss.v005.i08.
  12. G. Marsaglia and A. Zaman, “A new class of random number generators,” Annals of Applied Probability, vol. 1, no. 3, pp. 462-480, 1991. doi: 10.1214/aoap/1177005878.
  13. B. A. Wichmann and I. D. Hill, “An efficient and portable pseudorandom number generator,” Applied Statistics, vol. 31, no. 2, pp. 188-190, 1982. doi: 10.2307/2347988.
  14. E. A. Tsvetkov, “Empirical tests for statistical properties of some pseudorandom number generators,” Mathematical Models and Computer Simulations, vol. 3, pp. 697-705, 2011. doi: 10.1134/S207004821106010X.
  15. “The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness.” (2021), [Online]. Available: http:// ftpmirror.your.org/pub/misc/diehard/.
  16. P. L’Ecuyer and R. Simard, “TestU01: A C library for empirical testing of random number generators,” ACM Transactions on Mathematical Software (TOMS), vol. 33, no. 4, pp. 1-40, 2007. doi: 10.1145/1268776.1268777.
  17. L. E. Bassham, A. L. Rukhin, J. Soto, J. R. Nechvatal, M. E. Smid, S. D. Leigh, M. Levenson, M. Vangel, N. A. Heckert, and D. L. Banks, “A statistical test suite for random and pseudorandom number generators for cryptographic applications,” National Institute of Standards and Technology, NIST Special Publication, Gaithersburg, MD, Tech. Rep., 2010.
  18. A. A. Belov, N. N. Kalitkin, and M. A. Tintul, “Visual verification of pseudo-random number generators [Vizual’naya verifikatsiya generatorov psevdosluchaynykh chisel],” Keldysh IAM Preprints, Moscow, Tech. Rep. 137, 2019, In Russian. doi: 10.20948/prepr-2019-137.
  19. A. A. Belov, N. N. Kalitkin, and M. A. Tintul, “Unreliability of pseudorandom number generators,” Computational Mathematics and Mathematical Physics, vol. 60, no. 11, pp. 1747-1753, 2020. doi: 10.1134/S0965542520110044.
  20. I. M. Sobol, “Uniformly distributed sequences with additional uniformity properties,” USSR Computational Mathematics and Mathematical Physics, vol. 16, no. 5, pp. 236-242, 1976. doi: 10.1016/0041-5553(76)90154-3.

Copyright (c) 2021 Belov A.A., Tintul M.A.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies