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.
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.
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.
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?
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.
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.
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
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:
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.
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.
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://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=814...