Of course, this is more than just a cool mathematical trick - we show that structuring the computation in this way actually reduces thread divergence in parallel execution, which leads to some significant speedups on the GPU compared to Barnes-Hut.

However, this is equivalent to following every single path through the tree, and truncating paths that are less important to the sum. From here, we can make the algorithm stochastic (and unbiased!) by randomly selecting paths through the tree, and randomly truncating these paths.

The original, deterministic algorithm works by building an octree over all the source points, and essentially performing a truncated traversal over this tree that covers all the sources.

Meanwhile, stochastic approaches have been very successful in graphics - can we effectively use them here? We developed a stochastic version of the classic Barnes-Hut approximation that runs blazingly fast on the GPU, taking just 4ms to compute the total effect of over 4 trillion interactions!

Fast summation of interactions between a set of sources and a query point is a key ingredient in algorithms across science, engineering, and computer graphics, such as N-body simulation, winding number computation, and boundary integral evaluation.

At SIGGRAPH 2025, we’ll be presenting the paper “Stochastic Barnes-Hut Approximation for Fast Summation on the GPU”. By injecting a bit of randomization into the classic yet deterministic Barnes-Hut approximation for fast kernel summation, we can achieve nearly 10x speedups on the GPU!