4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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, 2016 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, 2016 at 5:11

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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, 2020 at 20:38
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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, 2016 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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