Fast Fourier Transform and Fast Multipole

Simulation of N-particle systems with pairwise interactions is a very common prob- lem that occurs in many fields in physics like N-body gravitation or electrostatics. Complete solution of this kind of problems involves evaluation of all pairwise in- teractions. So, if no modifications are made, one needs O(N2) calculations to completely solve the problem. It is obvious that increasing number of particles will make this type of problems very expensive. Therefore, finding methods to reduce the number of total calculations needed is of great importance. Main focus of this project is to investigate the effect of using two well known mathemati- cal methods, Fast Fourier Transform and Fast Multipole Methods, in speeding up N-body simulation problems. Fast Fourier Transform (FFT), a faster version of Discrete Fourier Transform, is an exact algebraic method which results in the exact solution by doing much less calculations. FFT reduces the amount of necessary calculations for N-particle simulation from O(N2) to O(N log(N)). FFT must be applied on a spatially uniform grid, and though it is not an obstacle in our problem in this project, it puts a limit on the applicability of FFT in general. Fast Multipole Method (FMM), is an approximate analytical method, which in a well defined problem will converge to exact solution very fast. Dissimilar to FFT, it does not require a uniform grid, and thus it is very useful in problems with few clusters of particles in a vacuum. FMM will reduce the cost of computations from O(N2) to O(N log(N)), and with some modifications to O(N). However, derivation of its formulation depends greatly on the type of interactions between particles. Therefore, on the one hand it needs a new effort for each new problem, and on the other hand it may be inappropriate for certain physical problems. Setting aside the differences in usability of FFT and FMM, we can compare their efficiency in speeding up the calculations as far as a problem where both can be applied is concerned. The final part of this project investigates run-time and computational cost of FFT and FMM through a detailed comparison