FMM-based Serial Beam-Beam Interaction Code

**Paul M. Alsing,
Vinay Boocha,
Mathias Vogt ^{1},
James Ellison
Albuquerque High Performance Computing Center
Department of Mathematics and Statistics
University of New Mexico
Albuquerque NM, 87131**

The essence of collective simulations of the beam-beam
interaction in particle colliders is
(1) the propagation of the particles in two counter
rotating bunches between adjacent interaction points through external fields and (2) the computation of the collective electromagnetic forces that the particles in one bunch exert on each of the particles of the other bunch, localized at the interaction points. The first part is straight forward and can be naively parallelized by assigning subsets of particles to different processors, and propagating them separately. The second part encompasses the core computational challenge which entails the summation of the collective effects of the particles in one beam on the individual particles in the other beam. Typically, for high energy colliders the computation of the collective forces is reduced to a 2 dimensional Poisson problem with Green's function proportional to
[1]. If there are particles in each beam, a brute force calculation involves computations. For moderate size N, this can quickly becomes a prohibitively expensive operation. Fast Multipole Methods (FMM) are often invoked to reduce the number of calculations to
[2,1].
Thus, current parallel implementations of FMM are inadequate for such simulations. In this work we describe a very simple parallelization of a FMM based beam-beam interaction code. We continue to use a serial FMM algorithm, but imbed it in a clever parallel communication scheme called Force Decomposition (FD) [4], initially developed for molecular dynamics simulations. Without the FMM, each processor in the FD algorithm would perform an brute force calculation, where
, where is the total number of processors used. By replacing this brute force computation with a serial FMM algorithm on each processor we reduce the computational complexity to
.
The advantage of this combined FMM/FD parallel method is that is extremely easy to implement. The FD method itself involves only three calls to MPI routines, and core FMM calculations are performed exactly as in a serial based FMM code, just now on a reduced set of sources and target particles. We demonstrate the speedup of of our parallel code over a serial code and indicate directions for future work to increase the order of this speedup.