Multipole Methods for the Masses | Hacker News Reader

Multipole Methods for the Masses

andyljones.com

82 pointsandyljones28 comments

Seeing this reminds me that, in 2000, the IEEE put together a list of what they considered the 10 most important algorithms of the 20th century [1]. The fast multipole method was one of them, along with the obvious heavy-hitters of FFT, quicksort, Metropolis-Hastings, and simplex.

[1] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=814...

Thanks for sharing that list. Is there a good reference that lucidly explains the basics of all (or most of) those algorithms? IMHO readable pseudocode would also be helpful.

Good list, the QR algorithm is particularly beautiful I think.

Personally, I think it's too oriented towards numerical algorithms. I'd drop the integer relation detection for RSA or maybe Diffie-Hellman as the most important cryptographic developments in the 20th century.

DH feels more important there.

I didn’t look at your scripts, but this page is very poorly behaved on Mobile Safari — it seems to refresh the whole page after the animations complete, which scrolls all the way up and then back down. It’s extra bad under excessive server load, because the refresh can fail.

Oh rats. Thanks for the heads up. I don't have an iPhone and it's not happening on macOS Safari. I'll have a Google around and see if any of the underlying libraries are likely culprits.

Which animation resetting seems to trigger it? Do you know which version of iOS/Safari you're using?

I’m on 13.4.1. I have no idea which animation is triggering it.

It seems to be fixed now. Thanks.

A while back I was learning about doing high quality approximate fluid simulations. If you take the curl of the Navier-Stokes equation and quantize (perhaps not the right word), you can simulate a collection of vortex particles that generate the velocity vector field, which is then used to advect those particles to get the next simulation step. Constructing the field is expensive and (now I know what it's called) you can use the multipole method to approximate it, since clusters of vortex particles, from far enough away, behave like a single particle whose vorticity is the sum of the vorticities of the particles.

I could never get the boundary conditions right (it involves generating vortex particles to neutralize torques), but it was still a lot of fun. The benefit of this method is that energy can be conserved and fine scale structures remain mostly intact, which is important for turbulent flows.

> quantize

Do yo mean "discretize"?

I don't think so, because the simulation uses vortex particles with continuous positions. Sure, time is discretized, but space is not, like how grid-based methods are.

the (in)famous Imperial model is not much different in nature. It's an agent-based and capable of making nice pictures like this.

https://github.com/mrc-ide/covid-sim/

However i have not been able to find a case where their model could reproduce the epidemiology of a previous epidemic like influenza.

Funnily enough, this entire project sprung out of my trying to replicate the Imperial model a month ago. I found the slow part was the community transmission kernel, and was surprised to find no epidemiological literature on applying fast multipole methods to the problem. I was even _more_ surprised to find there was no easy-to-use black-box fast multipole method implementation out there.

So I wrote one! It felt like a nice balance between 'doing something useful' and 'stepping on epidemiologists' toes'.

Incidentally, I believe the Imperial model solves things by dividing the region up into cells of ~half a km across and assuming everyone in the cell is at the center. I didn't know this when I started the project, but kinda assumed it'd do something like that when I couldn't find any work on FMM in epidemiology.

thanks for doing this. YEs, the imperial model seems to be "Simcity for pandemics", but i m not sure why it was considered reliable since it wasnt ever calibrated to match a real world epidemic

Did you tell the authors about your algorithm?

I sent some emails and didn't hear anything back. I'm hoping this post'll get organic attention for it, and I intend on sending more emails and - now you've prompted me! - opening an issue on the tracker too.

This algorithms is obviously used in solving the n-body problem (references to gravity fields and electric fields in the article).

I have a question. Although the article clearly states that this is not an epidemiological problem, I wonder about the following: gravity and electric fields are 1/r^2 type problems. I imagine that disease transmission depending on distance is a rather different thing, such as "high in immediate vicinity to the other point and then falling off quickly".

Do we know if the algorithm is accurate enough for this kind of "field"? Is it in general enough accurate or only for 1/r^2 type fields?

Short answer: yes, the underlying black-box fast multipole method will be very accurate with just a small number of Chebyshev coefficients. The main requirement is the kernel is reasonably smooth away from the origin.

Here's a toy example, 100 sources and points over a 10x10 square and a 1/(1 + d^2) kernel:

https://colab.research.google.com/drive/1F5rGIPxI8RI9tYJ4RSv...

Here, it gets 1e-8 residual variance.

Exactly which kernel to use for disease transmission is an open question, but IIRC the Imperial model used something like 1/(1 + d^(3/2)) based on fits to data.

1/r^2 fields are the gradients of 1/r potentials (not all efields are 1/r^2 btw). What is the potential in the case of disease transmission?

disease transmission can be modeled as a stochastic process and you can dig up a relationship to similar type methods (basis methods for solving odes) through the feynman-kac formula.

Really lovely animations, great for illustrating a quite complex algorithm. It would be nice to have a button to pause the animation at its end state to compare the curve shape and number of calculations.

That's a good idea - I'll have a think about how best to implement it. Might fall under the general category of 'add a speed control'.

Yeah just realised you're running the algorithms in real time in the browser so makes it a bit tricky. Maybe just have them pause when they reach the end state and have to click the play button to re-run.

That was really lovely pedagogy. Great use of animations (do you have a trick for effectively making them?)

Looking at the source they made the visualizations using Observable [1] which is using D3 under the hood.

[1] https://observablehq.com/

Yup! You can see the animations and their code in isolation here[1] - just click next to the animation to expand it. Fair warning, this is code I expected to write once and read never, and it shows.

[1] https://observablehq.com/d/dd1d583b63fccafd

This is really impressive. What would it take to persuade you to fix the 3D performance issues? :)

Very nicely written explanation!

Reply on news.ycombinator.com