Welcome to Fei Xue’s Homepage

P AMSC 663-664 Project

Computing the dynamics of large multi-particle systems using fast multipole method with multi-scale time stepping

Supervisors: Ramani Ruraiswami, Nail Gumerov

Abstract: The main task of my project is to implement a simulator computing the dynamics of large multi-particle systems based on parallelized Fast Multipole Method (FMM) and multi-scale time stepping integrator. The FMM computes the long range forces among the particles, and the integrator works out the positions and velocities of the particles at each time step. Both techniques require efficient partitioning of particles to cluster nodes such that the load balancing, communication cost and data locality issues are taken good care of. In particular, a key of partitioning is to reduce the cost of locating nearby and remote particles in the FMM tree so that the gain from multi-scale time stepping can indeed be achieved. There are some other important considerations, including collision detection and simulation, self-adaptive time step in execution and prevention of energy drift.

Context: The N-body problem, for which no general analytical solution exists, has many applications in astrophysics, molecular dynamics and fluid dynamics. Efficient simulation of such large multi-particle systems is an important problem in computational science. The direct computation of pairwise long-range force such as gravity and Coulomb force entails O (N ²) operations, which is multiplied by the time steps to be the total computation cost. One major category of methods is the tree/FMM algorithms which come from the observation that the effect of a group of particles on any distant particle can be approximated by a virtual particle at the centroid of the group. These methods compute all forces in each time step with O (N log N) or O (N) operations. The idea of multi-scale time stepping is to compute the forces given by nearby particles in each time step, and consider the forces from remote particles as constants in several successive steps. The two algorithms, when combined and parallelized efficiently, can become a powerful simulator to compute the dynamics of large multi-particle systems.

Proposal PDF PowerPoint

Progress Report PDF PowerPoint

Final Report PDF PowerPoint

P Teaching

P Research

P Friends

P Miscellaneous