Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

An Object-Oriented Implementation of the fast Multipole Method

: Müller, L.; Müller, W.
: Fraunhofer-Arbeitsgruppe für Graphische Datenverarbeitung -AGD-, Darmstadt

Darmstadt, 1990
Technical Report
Fraunhofer IGD ()
fast multipole method; object-oriented design; Particle based Modeling; particle interaction

The visualization and simulation of physical processes and the modelling of natural phenomena plays an increasing role in computer science. More and more the computer is used to simulate and to visualize the behaviour of biodies under stress or under other influences. Especially techniques like physical and particle-based modelling need to handle multi-body interactions. In general, the calculation of the effects of such multi-body interactions is very time consuming. The Fast Multipole Method represents an approach to accelerate the interaction calculations between particles for the specific case that the particle interactions can be expressed by the means of potential functions. The fast Multipole Method is based on the principle that a certain distance the interaction of an ensemle of charged particles can be approximated by one interaction with multipole representing the ensemble. For this purpose an octree structure is used, where the charged particles are inserted into the leafs. In the first step, the potentials are collected from the leafs upwards to each inner node. Thereafter, each inner node represents the corresponding multipole of its subtree. In a second phase the potentials of the effecting multipoles are collected and distributed to the children. Afterwards, every leaf possesses an expansion which describes the potential of the effecting multipoles. The evaluation of this function combined with the direct interaction calculation with all neighbours leads to the desired result. As an advantage of this algorithm, the time for the interaction calculation increases linearly with respect to the number of particles taking part in the interactions. Moreover, using this approach an arbitrary good approximation of the interaction forces can be achieved. This paper gives an introduction into the theory of the Fast Multipole Method. Some of the underlying concepts of this method are analysed and improved. In a second step, the needed elements for a full implementation of the Fast Multipole Method are described and specified using an object-oriented approach and CLOS.