I've been trying to understand the Fast Multipole Method but not really getting anywhere.

It seems like the fastest mainstream N-body simulation algorithm, and I would like to implement it in an efficient javascript version, mostly for amusement in browsers.

My math is pretty weak, but my programming is strong, relatively speaking. For example, I'm not even sure what "expansion" means mathematically in this context.

Can the implementation of FMM be described simply with words? Or is understanding of the math required?

  • $\begingroup$ Your mileage may vary, but while I could imagine using an implementation of the Fast Multipole Method without understanding its mathematical justification, I would think a substantial understanding was needed to write and test an implementation. $\endgroup$ – hardmath Feb 1 '16 at 15:19
  • $\begingroup$ In terms of expansion: Expansion, or series expansion, is a method to approximate a function using a summation of a sequence of terms. The approximation gets better as more terms are added. See en.m.wikipedia.org/wiki/Taylor_series for more details. $\endgroup$ – Charles Feb 2 '16 at 5:11

Actually I might have found a good explanation of the algorithm here: https://github.com/davidson16807/fast-multipole-method

  • 2
    $\begingroup$ Perhaps you could add a few more words about how this link leads to an answer of your Question? What does it really explain about the algorithm that you found useful, esp. as regards understanding or not understanding the math per your Question's context? If a link should go bad, knowing more about what was originally there can help to replace or recover it. Also it gives a Reader more of a basis to decide whether a link is worth following. $\endgroup$ – hardmath Feb 1 '16 at 15:22

I've put together a graphical, non-mathematical explanation of the fast multipole method here.

The animations help a lot, but in words: the fast multipole method would be a lot less scary if it were called 'the recursive approximation method'. It constructs a hierarchy of approximations to the field you're trying to calculate, and uses the big approximations at big scales and small approximations at small scales.

The 'multipole' bit of the name comes from the traditional choice of approximation to use, a Laurent series. The Laurent series is defined around a 'pole', and multiple approximations make for multiple poles! But really, the choice of approximation is not the crucial bit of the whole scheme.

  • 1
    $\begingroup$ Please add the details to your answer. Link-only posts are not considered suitable for this site since the link may get broken in the future. $\endgroup$ – nicoguaro Jul 23 '20 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.