Walk on Decomposed Subdomains (WoDS)

A Hybrid Monte Carlo–Deterministic Solver for Elliptic PDEs

Awarded: 🏆 SIGGRAPH 2026 Best Paper Award
Authors: Clément Jambon, Mohammad Sina Nabizadeh, and Mina Konaković Luković
Institution: Massachusetts Institute of Technology (MIT)

---

📌 Overview

Elliptic partial differential equations (PDEs) are fundamental to various fields, including engineering and computer graphics. However, solving them on geometries that are either highly intricate or constantly changing remains a significant hurdle.

The Current Landscape: A Tale of Two Approaches

Historically, researchers have relied on two primary methodologies, both of which have distinct drawbacks:

The Innovation: WoDS

The authors propose a hybrid strategy that merges the geometric adaptability of Monte Carlo (MC) methods with the stability of deterministic global solvers.

The core logic is as follows:

1. Decomposition: The domain is split into simple, regular subdomains.
2. Local Estimation: MC is used to calculate local first-passage solution operators (known as Poisson kernels). Because the spatial scale is reduced, the walk lengths and variance are kept under control.
3. Global Assembly: These local operators are integrated into a sparse global system.
4. Deterministic Solve: A linear solve replaces the need for simulating long, discrete random walks across the entire domain.

The Trade-off: This method swaps stochastic variance for a fixed, resolution-dependent discretization bias. The result is a stable, reusable operator.

Key Advantages

• Geometry-Aware: High accuracy even with coarse discretizations.
• Efficient Updates: When geometry changes, only the affected local operators need to be recomputed.
• Versatile: Proven effective for microstructure simulation, streamline visualization, and flow-based path planning.

---

📚 Reference & Credits

Citation

@article{wods, 
  author = {Jambon, Cl\'{e}ment and Nabizadeh, Mohammad Sina and Konakovi\'{c} Lukovi\'{c}, Mina}, 
  title = {Walk on Decomposed Subdomains: A Hybrid Monte Carlo–Deterministic Solver for Elliptic PDEs}, 
  year = {2026}, 
  issue_date = {July 2026}, 
  publisher = {Association for Computing Machinery}, 
  address = {New York, NY, USA}, 
  volume = {45}, 
  number = {4}, 
  url = {https://doi.org/10.1145/3811340}, 
  doi = {10.1145/3811340}, 
  journal = {ACM Trans. Graph.}, 
  month = jul, 
  articleno = {132}, 
  numpages = {22} 
}

Acknowledgments

The authors express gratitude to:

• The reviewers for their feedback.
• Pavle Konaković (3D scene design/rendering).
• Rohan Sawhney, Bailey Miller, and Hamid Kamkari (discussions).
• Funding: Wistron Corporation, Siebel Scholars program, and the MIT Generative AI Impact Consortium.

---

🛠️ Technical Deep Dive: Elliptic PDEs

The goal of this section is to provide the intuition behind the work. Note: This explanation differs from the formal paper; for rigorous proofs, please consult the original publication.

Boundary Value Problems (BVPs)

Many physical phenomena—such as electrostatics, heat conduction, and steady-state potential flow—are modeled as BVPs. In these cases, we know the values on the boundary ($\partial\Omega$) and need to find the solution $u$ in the interior ($\Omega$).

1. Dirichlet Boundary Conditions

In a standard Laplace equation with Dirichlet conditions, the value is fixed on the boundary:

$\begin{cases} \Delta u = 0 & \text{in } \Omega \\ u = g & \text{on } \partial\Omega_D \end{cases}$

Visual Note: Imagine a square where you "paint" heat values (+1 or -1) on the edges; the interior fills in smoothly.

2. Mixed Boundary Conditions (Neumann)

More complex problems involve zero-Neumann conditions, where the derivative of the solution normal to the boundary is zero:

$\begin{cases} \Delta u = 0 & \text{in } \Omega \\ u = g & \text{on } \partial\Omega_D \\ \frac{\partial u}{\partial n} = 0 & \text{on } \partial\Omega_N \end{cases}$

In this scenario, isolines of the solution bend to meet the Neumann boundary at exactly $90^\circ$.

The Problem with Traditional Grids

When using Finite Differences (FDM), the solution often appears "pixelated." To resolve complex geometric curves, one must use an incredibly fine grid, which is computationally expensive.

Finite Element Methods (FEM) avoid pixelation but introduce a different nightmare: Mesh Generation.

• Scenario: If you are designing a car and move a mirror by 1cm, you might have to regenerate the entire complex mesh from scratch.

The WoDS Workflow

The following diagram illustrates how the hybrid approach bypasses these issues:

Implementation Warning: The code used for the blog's visualizations is for illustrative purposes and is not a production-ready reference implementation.