The structure described here is a quad-tree, which is a good way of storing spatial data. Each cell which contains more than 1 particle is divided into 4 smaller cells until each cell has at most 1 particle.
Since actual galactic simulations are in 3-D, cells are also 3-D and are divided into 8 smaller subcells, creating an oct-tree instead.
mrrobot
I'm a bit confused about this tree, is this tree constructed separately for each star or once for all the stars? If it's constructed once for all the stars, do we randomly select one star as the root and then search for the star for which we are computing forces on in the tree? Then how do we ignore ancestors along the way that are far?
Updog
@mrrobot, There is just one tree. There is no star at the root node. You can think of all nodes as spatial subdivisions, so the root node is the entire area. You keep making recursive spatial subdivisions until each star is in its own cell. Interior nodes store the total mass of all stars in the cell's spatial subregion. My understanding is that when you compute the forces on a star, you walk the tree to find other stars, but since you know the center of mass and total mass for all cells, you stop early and use the aggregate interior node when the L/D ratio is below a threshold.
jhibshma
Does Barnes Hut typically divide things such that each point gets its own area? It seems like it might be useful to have a minimum block size that could contain multiple points. This might ruin some of the beauty of the tree though.
418_touhenying
@jhibshma In 15-150, there was a threshold that you can change, so that you can achieve different precision.
BensonQiu
Why is the expected number of nodes touched lg N / (Theta)^2?
365sleeping
@BensonQiu The question is actually two fold: (1) why is it proportional to Log$N$ and (2) why is it inversely proportional to $\Theta^2$.
For 1, suppose the mass distribution is homogeneous. Increasing the total number of particles four times will generate 3 new cells. While these 3 new cells will contribute only relatively small force to the old one. Now, the increased number ($\Delta$$N$) is not dependent on $N$, but is only dependent on $\Theta$. Thus, when $N$ increases by a ratio (of four), the time required only has a constant increment, i.e. on the scale of Log$N$.
For 2, $l$ is the length of cell and $D$ is the distance. The number of nodes touched is proportional to the square of them as we are on a 2D plane. Thus, I guess that it should be cubic if we are on a 3D space (not reliable source found yet).
aeu
I found a very nice visual explanation of this algorithm here and here. It shows how the tree and spatial domain evolves with added particles.
The structure described here is a quad-tree, which is a good way of storing spatial data. Each cell which contains more than 1 particle is divided into 4 smaller cells until each cell has at most 1 particle.
Since actual galactic simulations are in 3-D, cells are also 3-D and are divided into 8 smaller subcells, creating an oct-tree instead.
I'm a bit confused about this tree, is this tree constructed separately for each star or once for all the stars? If it's constructed once for all the stars, do we randomly select one star as the root and then search for the star for which we are computing forces on in the tree? Then how do we ignore ancestors along the way that are far?
@mrrobot, There is just one tree. There is no star at the root node. You can think of all nodes as spatial subdivisions, so the root node is the entire area. You keep making recursive spatial subdivisions until each star is in its own cell. Interior nodes store the total mass of all stars in the cell's spatial subregion. My understanding is that when you compute the forces on a star, you walk the tree to find other stars, but since you know the center of mass and total mass for all cells, you stop early and use the aggregate interior node when the L/D ratio is below a threshold.
Does Barnes Hut typically divide things such that each point gets its own area? It seems like it might be useful to have a minimum block size that could contain multiple points. This might ruin some of the beauty of the tree though.
@jhibshma In 15-150, there was a threshold that you can change, so that you can achieve different precision.
Why is the expected number of nodes touched lg N / (Theta)^2?
@BensonQiu The question is actually two fold: (1) why is it proportional to Log$N$ and (2) why is it inversely proportional to $\Theta^2$.
For 1, suppose the mass distribution is homogeneous. Increasing the total number of particles four times will generate 3 new cells. While these 3 new cells will contribute only relatively small force to the old one. Now, the increased number ($\Delta$$N$) is not dependent on $N$, but is only dependent on $\Theta$. Thus, when $N$ increases by a ratio (of four), the time required only has a constant increment, i.e. on the scale of Log$N$.
For 2, $l$ is the length of cell and $D$ is the distance. The number of nodes touched is proportional to the square of them as we are on a 2D plane. Thus, I guess that it should be cubic if we are on a 3D space (not reliable source found yet).
I found a very nice visual explanation of this algorithm here and here. It shows how the tree and spatial domain evolves with added particles.
Some relative materials could be found here: http://beltoforion.de/article.php?a=barnes-hut-galaxy-simulator&hl=en&s=idPageTop#idPageTop