-Shell error analysis for Walk On Spheres algorithms》.pdf

Mathematics and Computers in Simulation 63 (2003) 93–104 -Shell error analysis for “Walk On Spheres” algorithms Michael Mascagni a , Chi-Ok Hwangb,∗,1 a Department of Computer Science, Florida State University, 203 Love Building Tallahassee, FL 32306-4530, USA b Innovative Technology Center for Radiation Safety, Hanyang University, HIT Building, 17 Haengdang-Dong, Sungdong-Gu, Seoul 133-791, South Korea Received 16 November 2002; received in revised form 16 November 2002; accepted 25 February 2003 Abstract The “Walk On Spheres” (WOS) algorithm and its relatives have long been used to solve a wide variety of boundary value problems [Ann. Math. Stat. 27 (1956) 569; J. Heat Transfer 89 (1967) 121; J. Chem. Phys. 100 (1994) 3821; J. Appl. Phys. 71 (1992) 2727]. All WOS algorithms that require the construction of random walks that terminate, employ an -shell to ensure their termination in a finite number of steps. To remove the error related to this -shell, Green’s function first-passage (GFFP) algorithms have been proposed [J. Chem. Phys. 106 (1997) 3721] and used in several applications [Phys. Fluids A 12 (2000) 1699; Monte Carlo Meth. Appl. 7 (2001) 213; The simulation–tabulation method for classical diffusion Monte Carlo, J. Comput. Phys. submitted]. One way to think of the GFFP algorithm is as an = 0 extension of WOS. Thus, an important open question in the use of GFFP is to understand the tradeoff made in the efficiency of GFFP versus the -dependent error in WOS. In this paper, we present empirical evidence and analytic analysis of the -shell error in some simple boundary value problems for the Laplace and Poisson equations and show that the error associated with the -shell is O(), for small . This fact supports the conclusion that GFFP is preferable to WOS in cases where both are applicable. © 20