# Help understanding and implementing fast multipole method for N-body

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?

• 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.
– hardmath
Feb 1, 2016 at 15:19
• 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. Feb 2, 2016 at 5:11

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.