<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jan 24, 2022 at 4:46 PM Ted Stern <<a href="mailto:dodecatheon@gmail.com">dodecatheon@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi Forest,<br><br>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.<br><br>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.<br></div></blockquote><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">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.<br><br>The key to FMM is that you can do the same thing in the other direction, finding the effect of everything <i>outside</i> 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).<br></div></blockquote><div><br></div><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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).</div></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Cheers,</div></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><font face="trebuchet ms, sans-serif">Dr. Daniel Carrera</font></div><div dir="ltr"><font face="trebuchet ms, sans-serif">Postdoctoral Research Associate</font></div><div><font face="trebuchet ms, sans-serif">Iowa State University</font></div></div></div></div></div></div></div></div></div></div></div>