Harmonic Caching for Walk on Spheres
Open Access
- 4 December 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 44 (6) , 1-15
Abstract
We present a variance reduction technique for Walk on Spheres (WoS) that solves elliptic partial differential equations (PDEs) by combining overlapping harmonic expansions of the solution, each estimated using unbiased Monte Carlo random walks. Our method supports Laplace and screened Poisson equations with Dirichlet, Neumann, and Robin boundary conditions in both 2D and 3D. By adaptively covering the domain with local expansion regions and reconstructing the solution inside each region using an infinite Fourier series of the harmonic function, our method achieves over an order of magnitude lower error than traditional pointwise WoS in equal time. While low-order truncations of the series typically introduce limited bias, we also introduce a stochastic truncation scheme that eliminates this bias in the reconstructed solution. Compared to recently developed caching algorithms for WoS, such as Boundary and Mean Value Caching, our approach yields solutions with lower error and fewer correlation artifacts.Keywords
Funding Information
- NSF (2403122, 2440472, 1844538)
This publication has 19 references indexed in Scilit:
- A bidirectional formulation for Walk on SpheresComputer Graphics Forum, 2022
- A theory of monte carlo visibility samplingACM Transactions on Graphics, 2012
- Radiance caching for participating mediaACM Transactions on Graphics, 2008
- A first-order analysis of lighting, shading, and shadowsACM Transactions on Graphics, 2007
- Radiance Caching for Efficient Global Illumination ComputationIEEE Transactions on Visualization and Computer Graphics, 2005
- Convergence properties of Monte Carlo functional expansion talliesJournal of Computational Physics, 2005
- Improved radiance gradient computation2005
- Simulating self-gravitating hydrodynamic flowsComputer Physics Communications, 1995
- Regional Monte Carlo solution of elliptic partial differential equationsJournal of Computational Physics, 1982
- Exact Monte Carlo solution of elliptic partial differential equationsJournal of Computational Physics, 1981