[EM] Exact spatial model probabilities?

Daniel Carrera dcarrera at gmail.com
Mon Jan 24 15:19:31 PST 2022


On Mon, Jan 24, 2022 at 4:46 PM Ted Stern <dodecatheon at gmail.com> wrote:

> Hi Forest,
>
> To digress from the topic a bit, there is an O(N) method for N-body
> problems which has been around since the 1980s. It is called the Fast
> Multiple Method.
>
> The essence of the method is that the effect of a group of objects can be
> approximated (outside a certain radius) as the effect of a single composite
> object. These composite objects can further be combined into larger scale
> composite objects. This is similar to Isaac Newton's approximation of
> gravitational effect being due to a point mass.
>

Not too similar though. Planets and stars are really well approximated by
spheres, and the Shell theorem tells you that the gravitational field from
a sphere is exactly identical to that of a point mass. The quadrupole
moments for a planet are not usually relevant except for problems that
require extremely high precision (most notably, studies of Saturnian
moons). Tree codes and the Shell theorem are more or less at opposite ends
in terms of levels of approximation. You wouldn't use a tree code for the
solar system, for example.


If you just stop there, this reduces the order of operations to O(N logN).
> That first stage of approximation is the effect of collections of masses on
> everything else in the Universe.  N-body simulations using this idea are
> called Barnes-Hut methods.
>
> The key to FMM is that you can do the same thing in the other direction,
> finding the effect of everything *outside* a given radius on the objects
> inside. That can also be described as a composite object -- a multipole.
> Then there is a similar set of outer-inner nested collections to convey
> information from the rest of the Universe to each individual particle.
> This brings the number of operations to O(N).
>


Fun fact, FMM only entered astronomy relatively recently, while it has been
dominant in particle physics for a very long time. The difference is that
the FMM methods from condensed physics are only faster than BH trees if the
N-body system is largely homogeneous. That's great for condensed matter
physics, but in astronomy we have ridiculously hierarchical systems and the
FMM that you'll find if you do a Google search will work poorly in
astronomy. It was only 8 years ago that someone developed a FMM that beats
BH for hierarchical systems (Dehnen 2014).

Cheers,
-- 
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220124/7f7761cb/attachment.html>


More information about the Election-Methods mailing list