This thesis develops Monte Carlo algorithms based on the walk on spheres (WoS) method to reliably solve fundamental partial differential equations (PDEs) like the Poisson equation on geometrically complex domains. Elliptic PDEs are a basic building block of algorithms and applications throughout science, engineering, and geometric computing. Yet despite decades of research on methods for solving such PDEs, conventional solvers still struggle to deal with the level of geometric complexity found in the natural world. A constant challenge is the need for spatial discretization, which traditionally involves dividing the domain into a high-quality volumetric mesh or grid to perform PDE-based analysis. Unfortunately, this approach does not scale well to modern computer architectures as it is inherently sequential and memory intensive. It also falters when dealing with imperfect data containing poorly-shaped elements or self-intersections. These shortcomings together hinder the ability of scientists, engineers and designers to analyze geometric data and iterate on designs.

Walk on spheres makes a radical departure from conventional PDE solvers by reformulating the problem in terms of recursive integral equations that can be solved using the Monte Carlo method, allowing it to avoid volumetric mesh generation and function space approximation altogether. Furthermore, since these integral equations closely resemble those found in light transport theory, one can leverage deep knowledge from Monte Carlo rendering to build new algorithms for solving PDEs.

In this work, we take inspiration from rendering to generalize WoS to solve a much broader set of linear elliptic PDEs on solid regions of ℝ^N . We develop complete "black box" solvers encompassing integration, variance reduction and acceleration. Our solvers share many benefits with Monte Carlo methods from rendering: no volumetric meshing, trivial parallelism, output-sensitive evaluation of the PDE solution and its gradient without the need to solve a globally-coupled system of equations, and the ability to handle geometric data of size and complexity that is essentially hopeless for grid-based techniques.

138 pages

Thesis Committee:
Keenan Crane (Chair)
Ioannis Gkioulekas
Matthew O'Toole
Gautam Iyer
Matt Pharr (NVIDIA)

Srinivasan Seshan, 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