# SC²S Colloquium - October 21, 2015

The Fast Multipole Method is a numerical technique allowing the calculation of long-ranged forces in the N-body problem with a time complexity of O(N). To do so, in a three-dimensional space, long-ranged particle to particle interactions taken into account via with Multipole expansion to Local expansion interactions (M2L). M2L can be seen as a convolution of two $(p+1) \times (2p+1)$ matrices, $p$ being the order of the expansions, which implies an expansive time complexity of O(p^4). However, in frequency domain the convolution becomes a simple entrywise product of complexity O(p^2), in accordance with the convolution theorem. This IDP focuses on implementing a Fast Fourier Transform acceleration of the M2L phase in the molecular dynamics simulation software ls1 mardyn. Taking into account certain symmetry relations in the expansions, an optimized code of the FFT can be used to improve space and time performances. The FFT acceleration is implemented using a pre- and post-processing scheme around the M2L phase and a memoized function to manage the transfer functions used during the M2L translations. Speedups of factor 2-9 were achieved for expansions with order p between 5 and 15.