Summer of Math Exposition

Presented by 3Blue1Brown 3blue1brown

The Fastest Gravity Algorithm You've Never Heard Of

Audience:

Tags: calculuscomputer-sciencecomplex-analysis

In wanting to make a gravity simulation with particles, I discovered an algorithm that has never been covered in full on YouTube before, which immediately caught my attention due to how fast it claimed to be. Normally with NN particles, calculating all pairwise gravity forces takes O(N2)O(N^2), however this algorithm achieves an approximation in O(N)O(N) and also has a bounded error which can be tuned.

The title may be somewhat clickbait since I am only in high school, but as my teachers had never heard of it, and judging from the lack of material on YouTube, I think it’s pretty unknown, even though it’s much faster than the Barnes-Hut algorithm (O(NlogN)O(N\log N)), which a lot of videos do cover.

In this video, I go over the mathematics behind the algorithm in how it computes forces and manipulates certain objects to achieve the speedup. I plan to discuss my implementation in a future video, where I also learnt a lot when trying to optimize it. The final result is a simulation of 120,000 particles updated at 60 fps.



Analytics

6.82 Overall score*
28 Rank
17 Votes
15 Comments

Comments

7.3

I really did like the unexpected use of complex analysis, I however do think that If I had not just completed complex analysis as a subject previously, I may not have been able to appreciate the elegance of this algorithm.

7

Too fast and technical overall. In particular, it’s quite hard for viewers to think through anything if they aren’t already fully in complex analysis mode.

8.1

Awesome stuff! And I’m excited for part two so I’ll have to keep an eye on the Tubes of You for when it appears.

6

The animations at the beginning and end are beautiful. Really cool to see these, and neat that they’re real-time simulations.

At the beginning, I assumed you were simulating particles in 3D, but several minutes into the video it becomes clear that it’s actually 2D, so it would help orient the viewer if you say upfront what the framework is.

The high-level explanation (what the goal of the video is) and the low-level explanations (the step-by-step work) are clear. But there could be more mid-level explanation tying the individual goals together. An outline or overview would be helpful to tell the viewer where we’re going, and it would situate the low-level explanations better as parts of the algorithm as a whole. You could also spend a bit longer at the beginning of each section setting up what we’re about to do and why. For example, why is “flipping” the word chosen to talk about turning a power series into a polynomial? I didn’t get it.

Overall, you definitely have a talent for making this kind of video, and I hope to see more from you!

6.8

clear explanation.

9

Simply wonderful! And you are so young!

4

The topic was extremely well-selected, and as you said, fairly unique on YouTube! I also really admired the depth of the project and the fact that you actually implemented it. Definitely points for that, well done.

I did have some feedback.

Firstly, I didn’t feel that each step in the explanation was particularly well-motivated. I think it would’ve helped to show the viewer the goals on the current slide because I was often left wondering why we were doing certain operations. What are we working towards in the current section?

Secondly, in a maths explainer I personally find it helpful to either have the maths described in-depth so that I can follow it step-by-step, OR watch a more visual approach without worrying too much about the exact derivations.

To me it felt that the video didn’t go all in on either approach. It didn’t have the slow pacing and detail of a more comprehensive explainer, but then it didn’t describe the algorithm in a very visual way either. As a result the explanation felt rushed at times - reading out a lot of equations on the screen without a lot of clarity.

I think the motivation could have been made clearer with a benchmark / comparison of approaches.

Of course these are just my opinions, like I said the project was impressive and inspiring. But the video explainer had room to improve for me, sorry :(

2.5

Good video topic, however the jargon and explanations are difficult to follow. I would not this video for an undergraduate level unless they are curious about coding implementation. The video seems to introduce the topic as a discussion piece and help understand the algorithm, however we get too lost into the notation and algebra to really appreciate the value.

It is not clear how through all the work in the video that we produce a result in O(n). This feels more like a lecture than an instructive video.

This video is going too in-depth in all the computational nuances for it to be interesting for the subject. For 30 minutes, I still feel like I don’t understand the subject, even with a mathematics and computer science background. It feels like a lecture.

I didn’t learn a lot as much as I was supposed to.

I feel that this creator understands it themselves, but presents it in a way that was not suited for the targeted audience.

I would improve the algebra discussions, provide more context on why it works rather than going through the math.

6.8

This is a very good video with beautiful visuals. It looks like it took a ton of time and effort to make. Nice work!

Constructive criticism (for future videos):

*Much of the delicate math occurred so quickly that it would be very difficult for someone who doesn’t already know the math to follow along. Of course, tradeoffs need to be made in terms of length of the video, etc., but it seems like some of the explanation could have been slowed down a bit.

Overall, you did an excellent job!

4.7

Motivation 1/2 Clarity ~0.5/2 Novelty 2/2 Memorability ~0.5/2

I didn’t much care for the “I’ve carved out this space so that my video will be original” framing of the introduction. In particular, it sort of promises that the video will be technical over intuitive, since you differentiate yourself from others by saying “nobody really goes into the math of it”. This is a fine motivation for yourself, but asking for it to be the viewer’s motivation as well seems a bit strange.

With this motivation for yourself, it forces you into a tough expository position, and I’m sympathetic to the difficulty here. The algorithm is complicated, with a bunch of interlocking parts, each of which needs to be explained in an appropriate order without ballooning the length of the video. I don’t know how well it’d be possible to do this, but the video as it stands asks a bit too much of my working memory. One thing that might have helped is more of an outline, a high-level description early on to let me more easily segment the various parts. (It’s not clear to me how much that would help, because of the complexity of the topic, but these kinds of structuring tools do tend to have more impact than than you’d think.)

The point when I really lost the plot was when flip operation was introduced. My first thought upon encountering the flip operation is “is this actually going to be useful later?” Clearly yes, which I think I see somewhat now (probably later than intended, around 19:00), which is that rather than treating clusters as single points as in Barnes-Hut, we instead treat clusters as multipole expansions; converting each cluster to a local expansion at the point we actually care about using the flip. Mid-video I was wondering if a different ordering might also have helped, delaying the details of flip to after the multipole shift section?

Ultimately, you noted that this particular algorithm had not been well-covered by explainers before. Having now seen an admirable attempt at such an explanation, I think understand better why. If I had to give a single piece of advice to you, it would not be any particular improvement on your expository style, but just to be a bit more discerning during topic selection.

7.2

Neat algorithm!

sort of confusing with the details but the visuals make it much much clearer than it would otherwise be

8.5

Really great video! It was good that you didn’t show the really complicated algebra and instead focused on the important parts. Layout-wise, I liked the parts where on the left is some graphic and on the right the math. It helped visualizing what was being calculated.

7.4

Great introduction: showed a running model as proof-of-concept, made viewers curious about how the simulation was created. Interjections & corrections should remain on-screen long enough to be read and should correct the incorrect information. “Heirarchical” is the correct word. Large amounts of technical mathematics in the middle could get some people lost, but it was of the correct difficulty. Ending echoed the beginning, showing the running model once more, allowing the viewer to reflect on how far we’d come.

6.5

I can tell the video is clearly outlining all of the relevant math necessary for the explanation and lining it up well with the visuals. It was a little too fast, so slowing down the explanations and spending a little more time so that the equations and visuals can synchronize for the viewer would be helpful. At the pace its given, I would have to be a grad student or watch the video multiple times to understand what happened.

It would also help to add a little more relevance by comparing the simulation times to the N^2 or Nlog(N) algorithms for the specific animation you made at the beginning/end.

Overall its a great video with clear visuals, good music, and step-by-step instructions. No doubt if I ever tried to program this algorithm myself I would come back to this.

3.5

very hot