Parallel Implementation of the Fast Multipole Method with Periodic Boundary Conditions

We implement the Fast Multipole Method in three dimensions with periodic boundary conditions in a shared memory model. We alter Greengard's original formulae to a form more suitable for efficient computation. Then we derive an Ewald-type formulation for periodic boundary conditions especially adapted for the Fast Multipole Method. Operation counts of the dominating routines in the Fast Multipole Method lead to a performance model, whose predictions we verify experimentally. The parallel implementation on a shared memory machine is achieved with pthreads of the draft POSIX standard