We present a novel stochastic version of the Barnes-Hut approximation. Regarding the level-of-detail (LOD) family of approximations as control variates, we construct an unbiased estimator of the kernel sum being approximated. Through several examples in graphics applications such as winding number computation and smooth distance evaluation, we demonstrate that our method is well-suited for GPU computation, capable of outperforming a GPU-optimized implementation of the deterministic Barnes-Hut approximation by achieving equal median error in up to 9.4x less time.
@inproceedings{Madan:2025:stochastic-barnes-hut,
author = {Madan, Abhishek and Sharp, Nicholas and Williams, Francis and Museth, Ken and Levin, David I.W.},
title = {Stochastic Barnes-Hut Approximation for Fast Summation on the GPU},
year = {2025},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3721238.3730725},
doi = {10.1145/3721238.3730725},
booktitle = {ACM SIGGRAPH 2025 Conference Papers},
}
This project was funded in part by an NSERC Discovery Grant (RGPIN-2023–05120) and an Ontario Early Researchers Award. The first author was funded by an NSERC Canada Graduate Scholarship — Doctoral. We thank the attendees of the GraphQUON workshop for useful early discussions, and Mark Harris and Lars Nyland for proofreading.