This thesis develops the walk on spheres family of Monte Carlo PDE solvers into a practical computational framework for solving linear elliptic boundary value problems. Walk on spheres is effective for the same reason Monte Carlo rendering is: both recast their governing equations–elliptic PDEs and light transport–as integral equations that admit recursive Monte Carlo estimators, and both inherit the geometric scalability and robustness that follow from sampling rather than meshing. Yet where rendering matured over the past three decades into a ubiquitous, practical tool, walk on spheres still lacks the corresponding building blocks: support for more general boundary conditions, generalizations to participating media, caching and reuse schemes for accelerated evaluation, and differentiable variants for shape optimization. We take direct inspiration from the methods in rendering that provide these capabilities.

We generalize walk on spheres to first-order linear boundary conditions, broadening it beyond pure Dirichlet problems to the wider range of physically meaningful boundary models, much as general reflectance models did for rendering. We extend the method to participating media, solving linear elliptic boundary value problems on the same intricate microparticle geometries that volume rendering handles. We introduce caching and reuse schemes, in the spirit of virtual point lights and irradiance caching, that produce efficient and smooth dense solution estimates. Finally, we develop differential walk on spheres, computing solution derivatives through a nested boundary value problem that walk on spheres solves recursively, in analogy to differentiable rendering. Together, these contributions elevate walk on spheres from a geometrically capable estimator into a practical and extensible framework for Monte Carlo PDE simulation, mirroring the trajectory of Monte Carlo rendering.

93 pages

Thesis Committee:
Ioannis Gkioulekas (Chair)
Keenan Crane
Nicholas Boffi
Ravi Ramamoorthi (University of California, San Diego
Mathieu Desbrun (Inria / École Polytechnique)

Jignesh Patel, Interim Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu