In English

Fast Fourier Transform and Fast Multipole

Atefeh Kazeroonian
Göteborg : Chalmers tekniska högskola, 2011. 35 s.
[Examensarbete på avancerad nivå]

Simulation of N-particle systems with pairwise interactions is a very common prob- lem that occurs in many elds 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 modi cations 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, nding methods to reduce the number of total calculations needed is of great importance. Main focus of this project is to investigate the e ect 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 de ned 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 modi cations 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 e ort for each new problem, and on the other hand it may be inappropriate for certain physical problems. Setting aside the di erences in usability of FFT and FMM, we can compare their eciency in speeding up the calculations as far as a problem where both can be applied is concerned. The nal part of this project investigates run-time and computational cost of FFT and FMM through a detailed comparison.

Publikationen registrerades 2012-09-12. Den ändrades senast 2013-04-04

CPL ID: 163220

Detta är en tjänst från Chalmers bibliotek