State of the Art in Grid-Free Monte Carlo Methods for Partial Differential Equations
Abstract: Accurately analyzing large amounts of geometric data is critical for many scientific and engineering applications. Techniques based on partial differential equations (PDEs) provide powerful tools for analyzing physical systems, but conventional solvers are not at a stage where they “just work” on problems of real-world complexity. A constant challenge is spatial discretization, which divides the domain into a high-quality volumetric mesh or background grid for PDE-based analysis. Unfortunately, this approach does not scale well to modern computer architectures, and as such, there remains a large divide between our ability to visualize and analyze the natural world.
The walk on spheres (WoS) algorithm makes a radical departure from conventional PDE solvers, by reformulating fundamental PDEs like the Poisson equation as recursive integrals that can be solved using the Monte Carlo method. Since these integrals closely resemble those in light transport, one can leverage deep knowledge from Monte Carlo rendering to build new scalable algorithms with vastly different numerical tradeoffs, such as avoiding volumetric meshing altogether.
This course, presented at SIGGRAPH 2025 and the Symposium on Geometry Processing Graduate School 2024, provides a broad overview of grid-free Monte Carlo methods for PDEs, with an emphasis on teaching the key principles of Monte Carlo methods, from sample generation and variance reduction to system design, by ways of WoS and its recent generalizations.
SIGGRAPH 25 course material: abstract, slides [keynote (1.2 GB), pdf (400 MB)], recording (coming soon), ACM Library
SGP 24 course material: slides [keynote (1 GB), pdf (100 MB)], live recording
Associated publications and code
The course material is based on the following publications:
Monte Carlo Geometry Processing [Project, Paper, PhD thesis, Talk]
Walk on Stars: Grid-Free Monte Carlo for PDEs with Neumann Boundary Conditions [Project, Paper, Talk]
Walkin’ Robin: Walk on Stars with Robin Boundary Conditions [Project, Paper]
Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients [Project, Paper, Talk]
Boundary Value Caching for Walk on Spheres [Paper, Talk]
All solvers and geometric queries are implemented in the open-source Zombie and FCPW libraries (respectively). Also checkout the following starter code samples:
WoS in One Weekened
WoS for Laplace
WoS for Poisson
WoSt step-by-step tutorial
Additional aWoSome resources (will be updated regularly)
WoS is based on several rich concepts at the intersection of Monte Carlo methods, PDEs, and stochastic differential equations: from a harmonic analysis perspective, WoS is a Monte Carlo method for solving Laplace equations, while from a random process perspective, it is an acceleration strategy for simulating Brownian motion. Here are some recommended reference resources if you would like to dive further into these topics:
CMU 21-387: Monte Carlo Methods and Applications [Course webpage]
Monte Carlo Methods - a special topics course [Book]
Physically Based Rendering: From Theory To Practice [Book] - Goto reference for MC rendering
Harmonic Function Theory [Book]
Partial Differential Equations by Lawrence C. Evans [Book]
Stochastic Differential Equations by Bernt Øksendal [Book]
Handbook of Brownian Motion - Facts and Formulae [Book]
Einstein’s Investigations on the Theory of Brownian Movement from 1926! [Book]
Some Continuous Monte Carlo Methods for the Dirichlet Problem [Mervin Muller’s original paper on WoS]
The Rate of Convergence of the Walk on Spheres Algorithm [Paper]
WoS has recently seen growing interest in computer graphics, as it shares many computational benefits with Monte Carlo rendering: logarithmic scaling with geometric detail, robustness, trivial parallelism, output-sensitive evaluation, and the ability to work with different geometric representations. Beyond our own work on the topic, here is a non-exhaustive list of publications on advanced/alternative WoS estimators:
Differential Walk on Spheres [Project, Paper]
A Differential Monte Carlo Solver For the Poisson Equation [Project, Paper]
Solving Inverse PDE Problems using Monte Carlo Estimators [Project, Paper]
Kelvin Transformations for Simulations on Infinite Domains [Project, Paper]
Solving partial differential equations in participating media [Project, Paper]
Coupling Conduction, Convection and Radiative Transfer in a Single Path-Space [Project, Paper]
A Monte Carlo Method for Fluid Simulation [Project, Paper]
Velocity-Based Monte Carlo Fluids [Project, Paper]
Neural Monte Carlo Fluid Simulation [Project, Paper]
Stochastic Computation of Barycentric Coordinates [Paper]
Unbiased Differential Visibility Using Walk-on-Spherical-Caps and Closest Silhouettes [Project, Paper]
A Practical Walk-on-Boundary Method for Boundary Value Problems [Project, Paper]
Projected Walk on Spheres: A Monte Carlo Closest Point Method for Surface PDEs [Project, Paper]
Walk on Spheres for PDE-based Path Planning [Paper]
Heat Simulation on Meshless Crafted-Made Shapes [Paper]
Autonomous Exploration in Unknown Indoor 2D Environments Using Harmonic Fields [Paper]
Mesh‐free Monte Carlo method for electrostatic problems with floating potentials [Paper]
Monte Carlo Methods for 2D Flow Visualization [Paper]
as well as strategies for improving efficiency and increasing applicability to more boundary representations:
A Bidirectional Formulation for Walk on Spheres [Project, Paper]
Mean Value Caching for Walk on Spheres [Paper]
Neural Caches for Monte Carlo Partial Differential Equation Solver [Project, Paper]
Solving Poisson Equations using Neural Walk-on-Spheres [Paper, Code]
Conformal First Passage for Epsilon-free Walk-on-Spheres [Project, Paper]
Discontinuity-Aware 2D Neural Fields [Project, Paper]
Guiding-Based Importance Sampling for Walk on Stars [Project, Paper]
GPU-Accelerated Monte Carlo Geometry Processing for Gradient-Domain Methods [Paper]
Hierarchical Point Distance Fields [Paper]
Spelunking the deep: Guaranteed queries on neural implicit surfaces via range analysis [Project, Paper]
Ray Tracing Harmonic Functions [Project, Paper]
Also checkout these fun educational demos, blogs and tweets:
ShaderToy demos [implicit surface, curve inflation, diffusion curves]
Blogs [demofox, javascript implementation]
Tweets [MCGP, WoSt, Variable Coefficients, Path Planning]
Course contributors
Organizers and presenters
Rohan Sawhney
Bailey Miller
Ioannis Gkioulekas
Keenan Crane
Invited speakers
Wojciech Jarosz
Shuang Zhao
Mohammad Sina Nabizadeh
Zilu Li
Citation
Use the following BibTeX entries to cite this course:
@inproceedings{10.1145/3721241.3734001,
author = {Sawhney, Rohan and Miller, Bailey and Gkioulekas, Ioannis and Crane, Keenan},
title = {State of the Art in Grid-Free Monte Carlo Methods for Partial Differential Equations},
year = {2025},
isbn = {9798400715433},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3721241.3734001},
doi = {10.1145/3721241.3734001},
articleno = {3},
numpages = {8},
keywords = {Partial differential equations, Monte Carlo methods, walk on spheres},
series = {SIGGRAPH Courses '25}}
@inproceedings{Sawhney:2024:MCGP,
author = {Sawhney, Rohan and Miller, Bailey},
booktitle = {SGP 2024 Graduate School Courses},
title = {Monte Carlo Geometry Processing},
year = {2024}}
License
This tutorial is licensed under the CC BY 4.0 license.