Grid-free Monte Carlo for PDEs with spatially varying coefficients

1Carnegie Mellon University 2Dartmouth College

In ACM Transactions on Graphics (Proceedings of SIGGRAPH), 2022 (Awaiting publication)

Teaser
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.

Abstract

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.

Downloads

Acknowledgements

This work was generously supported by nTopology and Disney Research, NSF awards 1943123, 1812796 and 1844538, a Neukom Institute CompX faculty grant, a Packard Fellowship, and an NVIDIA Graduate Fellowship.

Cite

Rohan Sawhney, Dario Seyb, Wojciech Jarosz, Keenan Crane. Grid-free Monte Carlo for PDEs with spatially varying coefficients. ACM Transactions on Graphics (Proceedings of SIGGRAPH), 41(4), July 2022.
@article{sawhneyseyb22gridfree,
    author = "Sawhney, Rohan and Seyb, Dario and Jarosz, Wojciech and Crane, Keenan",
    title = "Grid-free {Monte} {Carlo} for {PDEs} with spatially varying coefficients",
    journal = "ACM Transactions on Graphics (Proceedings of SIGGRAPH)",
    year = "2022",
    month = jul,
    volume = "41",
    number = "4",
    doi = "10.1145/3528223.3530134",
    pubstate = "Awaiting publication",
    abstract = "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."
}