2 ms·
While the spatial decomposition matches what is done in Barnes-Hut, the details of the underlying algorithm are somewhat different (they outline this in the int
by radioactivist 3y ago
While the spatial decomposition matches what is done in Barnes-Hut, the details of the underlying algorithm are somewhat different (they outline this in the introduction).
In particular, their scheme using exact bounds on energy differences (evaluated using a hierarchical tree as in BH) but in such a way that no approximation is being made. The tree is evaluated to whatever depth is needed to decide whether to accept/reject the MC move (which in worse case could be a brute-force sum over the whole lattice/system) -- this is different I think than BH or other multipole inspired methods (which have a kind of "truncation" or "tolerance" parameter).
[This also works well with systems where update are local and not global, which I think is a difference from some other spatial partitioning schemes -- but I'm less conversant with that aspect].
- physicsguy 3y agoI read the full paper after posting my initial comment. Not really - BH does use a “opening angle” parameter, but for FMM you use an order of expansion which provides a strict error bound in terms of accuracy which was derived in Greengard and Rohklin’s original paper on but have been expanded to other potentials. To me it’s just a minor (but nonetheless interesting) variation of an existing method; there have been many of these. They don’t compare it to other tree based methods in performance in the paper which says to me that is merits aren’t really that clear… with long range potentials FP inaccuracies mean none of this is exact anyway.