peterzs / zombie

Grid-Free Monte Carlo PDE solvers

Zombie is a C++ header-only library for solving fundamental partial differential equations (PDEs) like the Poisson equation using the walk on spheres (WoS) method and its extensions. Unlike finite element, boundary element, or finite difference methods, WoS does not require a volumetric grid or mesh, nor a high-quality boundary mesh. Instead, it uses random walks and the Monte Carlo method to solve the problem directly on the original boundary representation. It can also provide accurate solution values at a single query point, rather than needing to solve the problem over the entire domain. This talk provides an overview of WoS, while the following papers discuss its present capabilities in greater detail:

Monte Carlo Geometry Processing [Project, Talk]
Walk on Stars: A Grid-Free Monte Carlo Method for PDEs with Neumann Boundary Conditions [Project, Talk]
Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients [Project, Talk]
Boundary Value Caching for Walk on Spheres [Paper]

WoS is a relatively new concept in graphics, rendering and simulation, and is an active area of research, e.g., 1, 2, 3, 4, 5, 6, 7. Therefore, the algorithms provided in this library are by no means optimal: further work is needed not just to make the Monte Carlo estimators more sample efficient, but also to extend the class of PDEs they can handle. Zombie aims to serve as a reference implementation for the current state of the art. Visit this repository for a step-by-step tutorial on the solver. A more optimized GPU implementation is currently in the works.

Concepts

At its core, Zombie solves PDEs of the form:

$$ \begin{array}{rcll} \Delta u &=& f & \text{on}\ \Omega, \\ u &=& g & \text{on}\ \partial\Omega_D, \\ \tfrac{\partial u}{\partial n} &=& h & \text{on}\ \partial\Omega_N, \\ \end{array} $$

where $\Omega$ is a domain in $\mathbb{R}^2$ or $\mathbb{R}^3$, and $f$, $g$ and $h$ are real-valued functions in $\Omega$, the Dirichlet part of the boundary $\partial\Omega_D$, and the complementary Neumann part of the boundary $\partial\Omega_N$ respectively. Zombie also supports screened Poisson equations with a constant absorption term (variable coefficients are not currently supported). Boundary conditions and source terms are provided as user-defined callback routines that return a value for any query point in the domain. Likewise, the domain boundary is queried using callbacks; Zombie currently supports boundaries represented as triangle meshes in 3D and line segments in 2D (see here), and uses the FCPW library to perform its geometric queries. The PDE solution (and optionally its spatial gradient) can then be evaluated at a set of user-specified evaluation points indepedently or through sample caching. The demo application demonstrates how to use the concepts defined in the library.

Compiling from source on Mac & Linux

git clone https://github.com/rohan-sawhney/zombie.git
cd zombie && git submodule update --init --recursive
mkdir build && cd build && cmake ..
make -j4

Citation

@software{Zombie,
author = {Sawhney, Rohan and Miller, Bailey and Gkioulekas, Ioannis and Crane, Keenan},
title = {{Zombie: A Grid-Free Monte Carlo Solver for PDEs}},
version = {1.0},
year = {2023}
}

Authors

Rohan Sawhney, Bailey Miller, Ioannis Gkioulekas, Keenan Crane

License

Code is released under an MIT License.