### Skapa referens, olika format (klipp och klistra)

**Harvard**

Kazeroonian, A. (2011) *Fast Fourier Transform and Fast Multipole*. Göteborg : Chalmers University of Technology

** BibTeX **

@mastersthesis{

Kazeroonian2011,

author={Kazeroonian, Atefeh},

title={Fast Fourier Transform and Fast Multipole},

abstract={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 modications 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 eect 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 dened 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 modications 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 eort for each new problem,
and on the other hand it may be inappropriate for certain physical problems.
Setting aside the dierences 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.},

publisher={Institutionen för teknisk fysik, Chalmers tekniska högskola},

place={Göteborg},

year={2011},

note={35},

}

** RefWorks **

RT Generic

SR Print

ID 163220

A1 Kazeroonian, Atefeh

T1 Fast Fourier Transform and Fast Multipole

YR 2011

AB 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 modications 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 eect 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 dened 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 modications 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 eort for each new problem,
and on the other hand it may be inappropriate for certain physical problems.
Setting aside the dierences 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.

PB Institutionen för teknisk fysik, Chalmers tekniska högskola,

LA eng

OL 30