
$$E(x_{j})=$$

![0_image_1.png](0_image_1.png)

## Where  Is The Electrostatic Constant.

In both of these, each body interacts with all the other, with an intensity that is inversely linear to the square of the distance. It is the same for Biot-Savart law, relative to both magnetism (under) and fluid dynamics [Leonard 1980]:

$$B(x)={\frac{1}{c}}\int J(y)\,{\frac{x-y}{|x-y|^{3}}}d y$$

## Where   Is The Current Density In .

The same can be written for diffusion, of heat for instance.

For all of these, structures of close entities play an important part. In gravitation, on different time scale they are the galaxies, solar systems, stars, planets. In magnetism, hydrodynamics and aerodynamics, congruence leads to vortexes or coils of different sizes, ranging from turbulence to the Gulf Stream or the red spot of Jupiter. In the Sun, congruence of plasma matter lead to sunspots and solar flare, and combined with fluids and gravity to coronal mass ejections.

## Life Sciences Examples

Many living systems can be described the same way [Simon 1996] [Frontier and Pichot-Viale 1998], with hierarchical spatial organizations. One of these models is the boids [Reynolds 1987]. We will apply our method to this model, so we will describe it in some depth. Boids are entities moving in a 2D or 3D space. They are ruled by quite simple rules, *Cohesion, Separation* and Alignment. Cohesion describes how boids try to fly in the direction of surrounding boids. Separation describes how boids are repulsed by other boids if these are really close. Alignment describes how boids try to fly in the same direction as the boids that environs them. A more formal description is:
Let j be a boid situated in the point  of an affine space.

Let () be its neighboring space, ie the set of boids not further from j than a certain limit at a given time t, excluding j itself.

Let be the speed of  at time . All the  below should be written but are conventionally simplified to easy up the reading.

We define: 

$$c_{t+1}^{j}=\sum_{i\in\eta(j)}{\frac{x_{i}}{\left\|x_{i}-x_{j}\right\|^{2}}}-x_{j}$$  $$s_{t+1}^{j}=\sum_{i\in\eta(j)}{\frac{\left(x_{j}-x_{i}\right)}{\left\|x_{i}-x_{j}\right\|^{3}}}$$
$$a_{t+1}^{j}=\sum_{i\in\eta(j)}\frac{v_{t}^{i}}{c a r d(\eta(j))\|x_{i}-x_{j}\|^{2}}$$

![0_image_0.png](0_image_0.png)

Which we combine:

$$v_{t+1}^{j}=\alpha v_{t}^{j}+\beta c_{t+1}^{j}+\gamma s_{t+1}^{j}+\delta a_{t+1}^{j}$$
Where $\alpha,\beta,\gamma,\delta$ are coefficients used to balance the 
different components of the speed.
This is for one species of boids. If *different* species of boids are considered, another stronger inter-species Separation is furthermore implemented to represent a tendancy to flock to their species and flee others [Dutot 2005]. Each species member speed is only influenced by its co-members as far as Alignment, Cohesion and intra species Separation are concerned. Each species can also have their own coefficients , ,  and .

## Hierarchical Methods To Accelerate The Computing

The computing of the relation above is of a complexity of the order of the square of the number of entities/bodies involved. This can be costly as the size of the simulation increases.

An often used technique to improve this is is to recursively divide the simulation space in a tree. The root of the tree encompasses the whole space. Its children are regular subdivision of the space, for example in 4 equal surfaces. The process is repeated recursively. We use an adaptive subdivision, which means regions of space containing many entities are more divided that sparser ones. The entities are associated to the leaves of the tree, which is adapted at each simulation step. The degenerated kernel relations described above are then computed. For that, the contribution of close entities is added exactly, while the contribution of further entities is averaged at the level of the leaf it belongs to. The exact economy is difficult to compute precisely as it depends on the structure of the tree, but it can be brought back to an average of () or even () [Beatson and Greengard] for  entities in the simulation. Furthermore, the loss of precision can be bound.

We originally used FMM in [Tranouez 2005] in a fluid flow simulation [Tranouez et al. 2005]. We discovered at the time that the tree used for the poles visually summarized the organizations appearing during the simulation (groups of vortexes of different shapes and sizes in this case). We therefore created an algorithm that formalized this visual discovery. We will now describe this method, on a boids application.

## The Method Relationship Between N-Trees And Organizations

As said above, the hierarchical subdivision of space can be represented by a tree whose root is the whole considered space and branches and leaves are subdivisions of this 