<p>Here's a partial answer: I don't have experience with direct-force simulations (<span class="math-container">$\mathcal {O}(N^2)$</span> methods), only with <span class="math-container">$\mathcal{O}(N\log\! N)$</span> methods, so I can't really say when you <em>should</em> use them, but I can perhaps provide some insight into when and why you <em>could</em> use them.</p>
<hr />
<h4>Simulating individual &quot;particles&quot;</h4>
<p>&quot;Direct-force&quot; methods are accurate in the sense that you calculate the actual gravitational forces between every single particle and every other particle (where &quot;particle&quot; can be e.g. a star). If you're interested in the dynamics of a star cluster which may have, say, <span class="math-container">$10^6$</span> stars packed in a small volume, you expect close encounters which may eject stars, form new binary systems, or even result in collisions, and you will want the forces to be calculated accurately. For <span class="math-container">$10^6$</span> stars, this will give you <span class="math-container">$\sim10^{12}$</span> calculations per time step which is a lot, but still feasible.</p>
<p>I'm not familiar with gyrfalcON, but judging from a quick look at the papers that have cited it, I think perhaps they tend to be interested more in streams of stars than in individual stellar interactions.</p>
<h4>Small-scale accuracy in large simulations</h4>
<p>Often, <span class="math-container">$N$</span>-body codes are used with many more particles, e.g. in the case of cosmological simulations where you simulate galaxy formation in a huge (Mpc- to Gpc-sized) volume. Here particles don't represent individual stars, but are rather tracers of dark matter. Hence, in such simulations &quot;the more the merrier&quot;: In principle you would like to simulate every single particle in the Universe, but that's impossible so you use one particle to represent, say, <span class="math-container">$10^5$</span> Solar masses of dark matter (the next step is hydrodynamic simulations where you also have particles representing gas, and stars). Therefore, the more particles you're able to use, the better resolution your simulation will have.</p>
<p>The largest such <span class="math-container">$N$</span>-body simulation to date is, I think, the AbacusSummit simulation (<a href="https://ui.adsabs.harvard.edu/abs/2021MNRAS.508..575G%2F/abstract" rel="nofollow noreferrer">Garrison et al. 2021</a>) which contains 60 trillion particles. With direct-force methods this would result in <span class="math-container">$\sim10^{28}$</span> calculations per time step, completely unfeasible on today's computers. Instead, simulations like this employ various methods such as oct-trees (where particles are grouped in larger and larger groups, the farther away they are from a given particle) or particle-mesh (where the total gravitational potential is calculated on a grid from which forces are interpolated). Such methods are <span class="math-container">$\mathcal{O}(N\log N)$</span>, so for the AbacusSummit you'd only have <span class="math-container">$\sim10^{15}$</span> calculations per time step. <strong>But in fact the underlying code, ABACUS, does use direct summation on small scales for accuracy</strong> (its complexity is still roughly <span class="math-container">$\mathcal{O}(N\log N)$</span> though).</p>
<h4>GPUs</h4>
<p>Because parallelization is easier on GPUs, direct summation may still be feasible on a relatively large number of particles. There are some codes that do this, e.g. NBODY6/7 and phiGRAPE, but I don't have any experience with this.</p>
<hr />
<p>So, to answer your question: You could use direct-force methods if you are interested in interactions between individual &quot;particles&quot; rather than overall dynamics, and don't need a large number of particles, e.g. if resolution is not an issue.</p>

CC BY-SA 4.0
2024-10-04T00:53:37.390Z
Have you answered "**When should we use** direct O(N^2) N-body simulation...?" The block quote in the question gives one good example; "These codes are often used in star cluster dynamics or in other contexts **where multiple stars and collisional (relaxation) effects are important.**" Are there other situations, or general rules of thumb, perhaps based on the importance of thermodynamical variables, when N-body *should be used?*
uhoh
CC BY-SA 4.0
2024-10-04T00:55:30.020Z
If it's answered and I'm just missing it (I've just started my first cup of coffee so I'm not firing on all cylinders) just let me know. :-)
uhoh
CC BY-SA 4.0
2024-10-04T12:18:01.780Z
@uhoh Are you referring to "could" vs. "should"? If so, the reason I said "could" instead of "should" is that I'm not sure you really _should_. It might be okay to use, say, tree methods for individual star simulations if the resolution is good enough. I don't have experience with such simulations, so I'm not comfortable saying "you should" (so perhaps I should've refrained from answering, but until a better answer comes up, this may be of some use).
pela
CC BY-SA 4.0
2024-10-04T13:59:23.100Z
Got it. I usually begin my partial answers with "Partial answer" as a courtesy to readers. and to those thinking they might also post an answer.
uhoh
CC BY-SA 4.0
2024-10-04T14:26:41.933Z
@uhoh Good point. Done!
pela
CC BY-SA 4.0
2024-10-02T13:24:51.437Z
2024-10-04T14:26:22.343Z
2024-10-04T14:26:22.343Z
pela
<p>I've read a <a href="https://td.lpi.ru/%7Eeugvas/nbody/tutor.pdf" rel="noreferrer">small tutorial</a> on N-body simulation methods. What it says about direct N-body simulation is:</p>
<blockquote>
<p>These codes are often used in star cluster dynamics or in other contexts where multiple stars and collisional (relaxation) effects are important</p>
</blockquote>
<p>I am a little confused as I discovered that many researchers in fact use NEMO's <a href="https://arxiv.org/pdf/astro-ph/0003209" rel="noreferrer">gyrFalcON</a> or some tree codes for cluster simulations. Does it mean that direct O(N^2) simulation is no use?</p>
<p>Are there ANY task from your experience where it is crucial to use direct O(N^2) N-body simulation (instead of other methods)?</p>

<software><n-body-simulations><star-cluster><globular-clusters><physics-simulations>
When should we use direct O(N^2) N-body simulation (instead of other methods)?
dust
# When should we use direct O(N^2) N-body simulation (instead of other methods)?

(Asked by: username_0 on 2024-10-01)

I've read a [small tutorial](https://td.lpi.ru/%7Eeugvas/nbody/tutor.pdf) on N-body simulation methods. What it says about direct N-body simulation is:

> These codes are often used in star cluster dynamics or in other contexts where multiple stars and collisional (relaxation) effects are important

I am a little confused as I discovered that many researchers in fact use NEMO's [gyrFalcON](https://arxiv.org/pdf/astro-ph/0003209) or some tree codes for cluster simulations. Does it mean that direct O(N^2) simulation is no use?

Are there ANY task from your experience where it is crucial to use direct O(N^2) N-body simulation (instead of other methods)?

**Tags:** software, n-body-simulations, star-cluster, globular-clusters, physics-simulations

---

## 1 answers

### Answer by username_1 on 2024-10-02. Score: 8

Here's a partial answer: I don't have experience with direct-force simulations ($\mathcal {O}(N^2)$ methods), only with $\mathcal{O}(N\log\! N)$ methods, so I can't really say when you *should* use them, but I can perhaps provide some insight into when and why you *could* use them.

---

#### Simulating individual "particles"

"Direct-force" methods are accurate in the sense that you calculate the actual gravitational forces between every single particle and every other particle (where "particle" can be e.g. a star). If you're interested in the dynamics of a star cluster which may have, say, $10^6$ stars packed in a small volume, you expect close encounters which may eject stars, form new binary systems, or even result in collisions, and you will want the forces to be calculated accurately. For $10^6$ stars, this will give you $\sim10^{12}$ calculations per time step which is a lot, but still feasible.

I'm not familiar with gyrfalcON, but judging from a quick look at the papers that have cited it, I think perhaps they tend to be interested more in streams of stars than in individual stellar interactions.

#### Small-scale accuracy in large simulations

Often, $N$-body codes are used with many more particles, e.g. in the case of cosmological simulations where you simulate galaxy formation in a huge (Mpc- to Gpc-sized) volume. Here particles don't represent individual stars, but are rather tracers of dark matter. Hence, in such simulations "the more the merrier": In principle you would like to simulate every single particle in the Universe, but that's impossible so you use one particle to represent, say, $10^5$ Solar masses of dark matter (the next step is hydrodynamic simulations where you also have particles representing gas, and stars). Therefore, the more particles you're able to use, the better resolution your simulation will have.

The largest such $N$-body simulation to date is, I think, the AbacusSummit simulation ([Garrison et al. 2021](https://ui.adsabs.harvard.edu/abs/2021MNRAS.508..575G%2F/abstract)) which contains 60 trillion particles. With direct-force methods this would result in $\sim10^{28}$ calculations per time step, completely unfeasible on today's computers. Instead, simulations like this employ various methods such as oct-trees (where particles are grouped in larger and larger groups, the farther away they are from a given particle) or particle-mesh (where the total gravitational potential is calculated on a grid from which forces are interpolated). Such methods are $\mathcal{O}(N\log N)$, so for the AbacusSummit you'd only have $\sim10^{15}$ calculations per time step. **But in fact the underlying code, ABACUS, does use direct summation on small scales for accuracy** (its complexity is still roughly $\mathcal{O}(N\log N)$ though).

#### GPUs

Because parallelization is easier on GPUs, direct summation may still be feasible on a relatively large number of particles. There are some codes that do this, e.g. NBODY6/7 and phiGRAPE, but I don't have any experience with this.

---

So, to answer your question: You could use direct-force methods if you are interested in interactions between individual "particles" rather than overall dynamics, and don't need a large number of particles, e.g. if resolution is not an issue.

> **Comments:**
> **username_2**: Have you answered "**When should we use** direct O(N^2) N-body simulation...?" The block quote in the question gives one good example; "These codes are often used in star cluster dynamics or in other contexts **where multiple stars and collisional (relaxation) effects are important.**" Are there other situations, or general rules of thumb, perhaps based on the importance of thermodynamical variables, when N-body *should be used?*  
> **username_2**: If it's answered and I'm just missing it (I've just started my first cup of coffee so I'm not firing on all cylinders) just let me know. :-)  
> **username_1**: @uhoh Are you referring to "could" vs. "should"? If so, the reason I said "could" instead of "should" is that I'm not sure you really _should_. It might be okay to use, say, tree methods for individual star simulations if the resolution is good enough. I don't have experience with such simulations, so I'm not comfortable saying "you should" (so perhaps I should've refrained from answering, but until a better answer comes up, this may be of some use).  
> **username_2**: Got it. I usually begin my partial answers with "Partial answer" as a courtesy to readers. and to those thinking they might also post an answer.  
> **username_1**: @uhoh Good point. Done!  

---

