Analysis and comparison of Green’s function first-passage algorithms with “Walk on Spheres” algorithms

Chi-Ok Hwang and Michael Mascagni

Mathematics and Computers in Simulation (MATCOM), 2003, vol. 63, issue 6, 605-613

Abstract: We analyze the optimization of the running times of Green’s function first-passage (GFFP) algorithms. The running times for these new first-passage (FP) algorithms [J. Chem. Phys. 106 (9) (1997) 3721; Phys. Fluids A 12 (7) (2000) 1699; J. Comput. Phys. 174 (2) (2001) 925; Monte Carlo Meth. Appl. 7 (3–4) (2001) 213], which use exact Green’s functions for the Laplacian to eliminate the absorption layer in the “Walk on Spheres” (WOS) method [Ann. Math. Stat. 27 (1956) 569; J. Heat Transfer 89 (1967) 121; J. Chem. Phys. 100 (5) (1994) 3821; J. Appl. Phys. 71 (6) (1992) 2727; J. Comput. Phys. 39 (1981) 396], are compared with those for WOS algorithms. It has been empirically observed that GFFP algorithms are more efficient than WOS algorithms when high accuracy is required [Phys. Fluids A 12 (7) (2000) 1699; J. Comput. Phys. 174 (2) (2001) 925; Monte Carlo Meth. Appl. 7 (3–4) (2001) 213]. Additionally, it has been observed that there is always an optimal distance from the surface of the absorbing boundary, δI, for a GFFP algorithm within which a FP surface can be permitted to intersect the boundary [Phys. Fluids A 12(7) (2000) 1699; J. Comput. Phys. 174 (2) (2001) 925; Monte Carlo Meth. Appl. 7 (3–4) (2001) 213]. In this paper, we will provide a rigorous complexity analysis consistent with these observations. This analysis is based on estimating the numbers of WOS and GFFP steps needed for absorption on the boundary, and the complexity and running times of each WOS and GFFP step. As an illustration, we analyze the running times for calculating the capacitance of the unit cube using both GFFP and WOS.

Keywords: Green’s function first-passage (GFFP); Walk on Spheres (WOS); Complexity analysis (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475403000910
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:63:y:2003:i:6:p:605-613

DOI: 10.1016/S0378-4754(03)00091-0

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().