N-body gravity simulation in O(N)

This is about the fast multi-pole for a gravity simulation in 2d. The basic trick, as far as I can tell, is to bin particles into a grid/octree and then group the particles in the boxes to speed up calculation. The multipole expansion inside the box is exact up to truncation error outside the radius of convergence?

For any particle in a grid cell, a sweep of the neighbors is walking the neighbors of the octree at different levels, leading to an O(1) cost, so an O(n) algorithm to process all particles. I'm still missing the details of how the adaptive FMM makes sure the runtime is kept linear when traversing neighbors that are in different cell sizes in the octree and, for me, the video didn't do a great job of explaining it.

Can this be done in 3d and still remain linear?

The video has the link to papers but for convenience here they are as well:

• "A Fast Algorithm for Particle Simulations" - L. Greengard, V. Rokhlin (1987)
• "A Fast Adaptive Multipole Algorithm for Particle Simulations" - J. Carrier, L.greengard, V. Rokhlin (1988)

As I was first reading the TSNE paper, it occurred to me that the core algorithm was straightforward and presented at the beginning. I wondered what on earth could the rest of these pages contain, and it turns out the non-algorithm details needed to get correct so the thing could be useful in practice are way harder.

I forget what they called it, but one detail was treating distant particles like a single entity when they're "far enough away" to avoid the N^2 calculation. I'm vaguely aware of others, like having enormous step sizes for the first hundred iterations or something, but I've definitely lost track of it.

My point is, a novel algorithm as useful as TSNE was inaccessible until the author broke through the practical challenges of using it, such as the [seemingly unrelated] N^2 gravity problem.