For more details, check out the full paper and our project site: www.dgp.toronto.edu/projects/sto...

There’s no free lunch - by adding randomization, we can increase the worst-case error. However, average errors are lower, and we’ve just scratched the surface of variance reduction techniques for this estimator, so the gap in max error can be closed even further.

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.