Walking on Spheres and Talking to Neighbors: Variance Reduction for Laplace's Equation

Walk on Spheres algorithms leverage properties of Brownian Motion to create Monte Carlo estimates of solutions to elliptic partial differential equations. We propose a new caching strategy that leverages the continuity of paths of Brownian Motion. Until recently, estimates were constructed pointwise and did not use the relationship between solutions at nearby points within a domain. In the case of Laplace’s equation with Dirichlet boundary conditions, our algorithm has improved asymptotic runtime compared to previous approaches. Our results are achieved by information reuse from a cache of fixed size. We also provide bounds on the performance of our algorithm and demonstrate our approach on example problems of increasing complexity.