4 ms·

Multipole Methods for the Masses

82 points by andyljones 6y ago

Gravityloss 6y ago
Very nicely written explanation!
ahh 6y ago
That was really lovely pedagogy. Great use of animations (do you have a trick for effectively making them?)
- blcArmadillo 6y ago
  Looking at the source they made the visualizations using Observable [1] which is using D3 under the hood. [1] https://observablehq.com/ https://observablehq.com/
  - andyljones 6y ago
    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 https://observablehq.com/d/dd1d583b63fccafd
barbegal 6y ago
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.
- andyljones 6y ago
  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'.
  - barbegal 6y ago
    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.
buboard 6y ago
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/ 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.
- andyljones 6y ago
  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.
  - buboard 6y ago
    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
  - amluto 6y ago
    Did you tell the authors about your algorithm?
    - andyljones 6y ago
      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.
amluto 6y ago
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.
- andyljones 6y ago
  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?
  - amluto 6y ago
    I’m on 13.4.1. I have no idea which animation is triggering it.
    - amluto 6y ago
      It seems to be fixed now. Thanks.
jcranmer 6y ago
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=814652 https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=814...
- augustt 6y ago
  Good list, the QR algorithm is particularly beautiful I think.
  - jcranmer 6y ago
    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.
    - tptacek 6y ago
      DH feels more important there.
- ssivark 6y ago
  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.
cgufus 6y ago
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?
- throwlaplace 6y ago
  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.
- andyljones 6y ago
  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/1F5rGIPxI8RI9tYJ4RSv85xdlfyEFT6Mk 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.
kmill 6y ago
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.
- hogehogefoo 6y ago
  > quantize Do yo mean "discretize"?
  - kmill 6y ago
    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.
Zaak 6y ago
This is really impressive. What would it take to persuade you to fix the 3D performance issues? :)

82 points by andyljones 6y ago

Gravityloss 6y ago

Very nicely written explanation!

ahh 6y ago

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

blcArmadillo 6y ago
Looking at the source they made the visualizations using Observable [1] which is using D3 under the hood. [1] https://observablehq.com/ https://observablehq.com/
- andyljones 6y ago
  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 https://observablehq.com/d/dd1d583b63fccafd

barbegal 6y ago

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.

andyljones 6y ago
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'.
- barbegal 6y ago
  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.

buboard 6y ago

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/ 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.

andyljones 6y ago
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.
- buboard 6y ago
  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
- amluto 6y ago
  Did you tell the authors about your algorithm?
  - andyljones 6y ago
    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.

amluto 6y ago

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.

andyljones 6y ago
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?
- amluto 6y ago
  I’m on 13.4.1. I have no idea which animation is triggering it.
  - amluto 6y ago
    It seems to be fixed now. Thanks.

jcranmer 6y ago

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

augustt 6y ago
Good list, the QR algorithm is particularly beautiful I think.
- jcranmer 6y ago
  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.
  - tptacek 6y ago
    DH feels more important there.
ssivark 6y ago
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.

cgufus 6y ago

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?

throwlaplace 6y ago
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.
andyljones 6y ago
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/1F5rGIPxI8RI9tYJ4RSv85xdlfyEFT6Mk 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.

kmill 6y ago

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.

hogehogefoo 6y ago
> quantize Do yo mean "discretize"?
- kmill 6y ago
  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.

Zaak 6y ago

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