# Building Upon Fast Multipole Methods To Detect And Model Organizations Pierrick Tranouez1,2 And Antoine Dutot1

1 LITIS
Université du Havre UFR Sciences et Techniques 25 rue Ph. Lebon - BP 540 76058 Le Havre Cedex - France
{Pierrick.Tranouez, Antoine.Dutot}@litislab.eu 2 MTG - UMR IDEES
Université de Rouen IRED
7 rue Thomas Becket 76821 Mont Saint Aignan Cedex - France

## Keywords

Organization detection, structure management, multiscale, N body systems, hierarchical tree code approximations

## Abstract

Many models in natural and social sciences are comprised of sets of interacting entities whose intensity of interaction decreases with distance. This often leads to structures of interest in these models composed of dense packs of entities. Fast Multipole Methods are a family of methods developed to help with the calculation of a number of computable models such as described above. We propose a method that builds upon FMM to detect and model the dense structures of these systems.

## Introduction

We study in this paper dynamic systems composed of many interacting entities. We are interested in their modeling, simulation, in the way they evolve and organize themselves.

Among these theoretical systems, a class of them is used as models for different natural science systems. In this class, systems verify the following properties:
1. Entities follow an analytical model 2. Each entity interacts with all the others.

3. The strength of the interactions decreases with the distance separating the entities implied in the relationship It is to this class that N-Body problems in physics belong to for example.

Property 2 makes computing a simulation through the iterative calculations of the model in 1 costly, in  
2 for entities. There are mathematical techniques to accelerate this computing, such as Fast Fourier Transform or Fast Multipole Methods. We will deal in this paper with hierarchical methods such as FMM.

Furthermore, systems of the class described above have also some remarkable properties in their organizations. As interactions intensity decrease with the distance and these interactions are often of an attractive nature, aggregate or clusters often emerge of their simulation, and play important parts as structures and organizations of the simulation.

We give in this article a method that detects and manages such organizations in this class of models, in connection with an FMM simulation (or hierarchical tree code approximations in general).

## Kernels And Fast Multipole Methods

The Introduction may give the impression that our organization-handling scheme works in only very restricted cases, but systems verifying these properties often appear in scientific literature [Beatson and Greengard].

## Physics Examples

Provided N bodies of mass  a description of the gravitational field in is Newton law [Newton 1686]:

$$g(x_{j})=\sum_{i=1\atop i\neq j}^{N}G m_{i}{\frac{x_{i}-x_{j}}{\left\|x_{j}-x_{i}\right\|^{3}}}$$

Where  is the gravitational constant. Similarly for N bodies of charge q, Coulomb law [Coulomb 1785] describes the electrostatic field in 
: