Breadcrumb
PyFMM project page
Contact information: see faculty profile.
Overview
Star systems are inherently discrete, as are systems of atoms or molecules.
This project deals with fast algorithms for calculating the interactions of many particles. Perhaps the most notorious of these algorithms is the fast multipole method (FMM), which was rated as one of the Top-10 algorithms of the 20th century. It is capable of dramatically speeding up calculations where N particles interact with each other —an N-body problem. Its first applications were found in calculating the gravitational field of N stars.
Particle simulations are used in two contexts. In the most natural application, particles are used to represent inherently discrete systems, such as a cluster of stars in space. In another application, particles are used as a means of discretizing or modeling a continuum. We are mainly interested in this second context, but some of the methods that we develop can be applied in both.
The FMM can be used in many scientific computing applications: the simulation of many stars, electrostatics, the calculation of atoms or molecules out of equilibrium, and particle methods for continuum problems. The advantages of the FMM can be huge when large numbers of particles are involved, as it reduces the complexity of calculations from O(N2) to O(N).
A more widespread adoption of the FMM algorithm has not occurred, mainly due to the complexity of the algorithm and the considerable programming effort, when compared with other algorithms like particle-mesh methods, or treecodes providing O(N log N) complexity.
We are developing an open source implementation of the FMM —with particular application to the calculation of a velocity field induced by N vortex particles— which will evolve to a full, parallel library component. The first incarnation of the code is a Python implementation, being made available to the wider academic community via a Google Codes project. In the second stage, we are developing a parallel implementation of the code, which will be distributed as an add-on component to the PETSc library for scientific computing.
Collaboration Group
- Felipe Cruz, PhD student
- Felipe is funded by a grant from BAE/Airbus to work on the development of hybrid particle-continuum methods and their implementation in novel computer architectures. He has written the Python prototype code, with which we have performed a suite of experiments investigating the errors of the FMM approximation.
- Dr Matthew Knepley, Argonne National Laboratory
- We are collaborating with Matt for the development of a parallel version of the FMM code, to be added to the PETSc library for scientific computing
Project results
A graph of the spatial errors in an experiment with the fast multipole method. The colors map to a logarithmic scale, where blue is 1e-16 and red is 1e-9.
Python implementation of the FMM
With PhD student Felipe Cruz, we are developing an open source FMM implementation, whose first incarnation is a Python prototype, written by Felipe. With this code, we have carried out a study of the errors of the FMM approximation, depending on the algorithm parameters. Preliminary results of these studies are being presented in the 8th World Congress on Computational Mechanics, Venice.
The source code of the Python implementation is made available to the wider academic community via Google Code project hosting.
Downloads
Characterization of the FMM approximation in particle simulations.
Abstract of the paper accepted for presentation at the 8th World Congress on Computational Mechanics, Venice (July 2008).
FMM for particle interactions: an open soure parallel library component.
Extended abstract submitted for presentation at the 20th Parallel Computational Fluid Dynamics conference, Lyon (May 2008).