Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients

Distribution of heat (inset) radiating from infinitely many blackbodies—about 600M effective boundary vertices are visible from this viewpoint alone. (Here we visualize a 2D slice of the full 3D solution.) Our Monte Carlo PDE solver directly captures fine geometric detail and intricate spatially varying coefficients without meshing, sampling, or homogenizing the 3D domain, by building on techniques from volumetric rendering.


Partial differential equations (PDEs) with spatially varying coefficients arise throughout science and engineering, modeling rich heterogeneous material behavior. Yet conventional PDE solvers struggle with the immense complexity found in nature, since they must first discretize the problem—leading to spatial aliasing, and global meshing/sampling that is costly and error-prone. We describe a method that approximates neither the domain geometry, the problem data, nor the solution space, providing the exact solution (in expectation) even for problems with extremely detailed geometry and intricate coefficients. Our main contribution is to extend the walk on spheres (WoS) algorithm from constant- to variable-coefficient problems, by drawing on techniques from volumetric rendering. In particular, an approach inspired by null-scattering yields unbiased Monte Carlo estimators for a large class of 2nd order elliptic PDEs, which share many attractive features with Monte Carlo rendering: no meshing, trivial parallelism, and the ability to evaluate the solution at any point without solving a global system of equations.

ACM Transactions on Graphics (Proceedings of SIGGRAPH)