Abstract
A Random Walk on Ellipsoids (RWE) algorithm is developed for solving a general class of elliptic equations involving second- and zero-order derivatives. Starting with elliptic equations with constant coefficients, we derive an integral equation which relates the solution in the center of an ellipsoid with the integral of the solution over an ellipsoid defined by the structure of the coefficients of the original differential equation. This integral relation is extended to parabolic equations where a first passage time distribution and survival probability are given in explicit forms. We suggest an efficient simulation method which implements the RWE algorithm by introducing a notion of a separation sphere. We prove that the logarithmic behavior of the mean number of steps for the RWS method remains true for the RWE algorithm. Finally we show how the developed RWE algorithm can be applied to solve elliptic and parabolic equations with variable coefficients. A series of supporting computer simulations are given.
Funding source: Russian Science Foundation
Award Identifier / Grant number: 19-11-00019
Funding statement: Support of the Russian Science Foundation under Grant 19-11-00019 is gratefully acknowledged.
References
[1] G. W. Brown, Monte Carlo Methods, Modern Mathematics for the Engineer, McGraw–Hill, New York (1956), 279–303. Search in Google Scholar
[2] B. M. Budak, A. A. Samarskiĭ and A. N. Tihonov, Book of Exercises in Mathematical Physics (in Russian), 3rd ed., “Nauka”, Moscow, 1980. Search in Google Scholar
[3] R. Courant and D. Hilbert, Methods of Mathematical Physics. Vol. II: Partial Differential Equations, Wiley Class. Library, John Wiley & Sons, New York, 1989. 10.1002/9783527617234Search in Google Scholar
[4] L. Devroye, The series method for random variate generation and its application to the Kolmogorov–Smirnov distribution, Amer. J. Math. Management Sci. 1 (1981), no. 4, 359–379. 10.1080/01966324.1981.10737080Search in Google Scholar
[5] E. B. Dynkin, Theory of Markov Processes, Pergamon Press, New York, 1961. Search in Google Scholar
[6] B. S. Elepov and G. A. Mikhailov, On the theory of estimates of the Monte Carlo method that are connected with a “random walk on spheres”, Sib. Math. J. 36 (1995), no. 3, 465–471. 10.1007/BF02109835Search in Google Scholar
[7] S. M. Ermakov, V. V. Nekrutkin and A. S. Sipin, Random Processes for Classical Equations of Mathematical Physics, Math. Appl. (Sov. Ser.) 34, Kluwer Academic Publishers Group, Dordrecht, 1989. 10.1007/978-94-009-2243-3Search in Google Scholar
[8] G. M. Fikhtengolts, A Course of Mathematical Analysis. Vol.3, Dover Books, Mineola, 2013. Search in Google Scholar
[9] A. Haji-Sheikh and E. M. Sparrow, The floating random walk and its application to Monte Carlo solutions of heat equations, SIAM J. Appl. Math. 14 (1966), 370–389. 10.1137/0114031Search in Google Scholar
[10] K. Itô and H. P. McKean, Jr., Diffusion processes and their sample paths, Grundlehren Math. Wiss. 125, Springer, Berlin, 1965. Search in Google Scholar
[11] G. N. Milstein and M. V. Tretyakov, Stochastic Numerics for Mathematical Physics, Sci. Comput., Springer, Berlin, 2004. 10.1007/978-3-662-10063-9Search in Google Scholar
[12] M. E. Muller, Some continuous Monte Carlo methods for the Dirichlet problem, Ann. Math. Statist. 27 (1956), 569–589. 10.1214/aoms/1177728169Search in Google Scholar
[13] A. P. Prudnikov, Y. A. Brychkov and O. I. Marichev, Integrals and Series (in Russian), “Nauka”, Moscow, 1981. Search in Google Scholar
[14] K. Sabelfeld and A. Kireeva, A new global random walk algorithm for calculation of the solution and its derivatives of elliptic equations with constant coefficients in an arbitrary set of points, Appl. Math. Lett. 107 (2020), Article ID 106466. 10.1016/j.aml.2020.106466Search in Google Scholar
[15] K. K. Sabelfeld, Monte Carlo Methods in Boundary Value Problems, Springer Ser. Computat. Phys., Springer, Berlin, 1991. 10.1007/978-3-642-75977-2Search in Google Scholar
[16] K. K. Sabelfeld, Random walk on spheres method for solving drift-diffusion problems, Monte Carlo Methods Appl. 22 (2016), no. 4, 265–275. 10.1515/mcma-2016-0118Search in Google Scholar
[17] K. K. Sabelfeld, A mesh free floating random walk method for solving diffusion imaging problems, Statist. Probab. Lett. 121 (2017), 6–11. 10.1016/j.spl.2016.10.006Search in Google Scholar
[18] K. K. Sabelfeld, Random walk on spheres algorithm for solving transient drift-diffusion-reaction problems, Monte Carlo Methods Appl. 23 (2017), no. 3, 189–212. 10.1515/mcma-2017-0113Search in Google Scholar
[19] K. K. Sabelfeld and I. A. Shalimova, Spherical and Plane Integral Operators for PDEs: Construction, Analysis, and Applications, De Gruyter, Berlin, 2013. 10.1515/9783110315332Search in Google Scholar
[20] K. K. Sabelfeld and N. A. Simonov, Stochastic Methods for Boundary Value Problems: Numerics for High-Dimensional PDEs and Applications, De Gruyter, Berlin, 2016. 10.1515/9783110479454Search in Google Scholar
[21] I. Shalimova and K. K. Sabelfeld, Random walk on spheres method for solving anisotropic drift-diffusion problems, Monte Carlo Methods Appl. 24 (2018), no. 1, 43–54. 10.1515/mcma-2018-0006Search in Google Scholar
[22] I. Shalimova and K. K. Sabelfeld, A random walk on small spheres method for solving transient anisotropic diffusion problems, Monte Carlo Methods Appl. 25 (2019), no. 3, 271–282. 10.1515/mcma-2019-2047Search in Google Scholar
© 2020 Walter de Gruyter GmbH, Berlin/Boston