Numerical fourier transform and its usage : An introduction

The aim of this bachelor's thesis is to use three variants of the discrete Fourier transform (DFT) and compare their computational cost. The transformation will be used to numerically solve partial differential equations (PDE). In its simplest form, the DFT can be regarded as a matrix multiplication. It turns out that this matrix has some nice properties that we can exploit. Namely that it is well-conditioned and the inverse of the matrix elements is similar to the original matrix element, which will simplifies the implementation. Also, the matrix can be rewritten using different properties of complex numbers to reduce computational cost. It turns out that each transformation method has its own benefits and drawbacks. One of the methods makes the cost lower but can only use data of a fixed size. Another method needs a specific library to work but is way faster than the other two methods. The type of PDE that will be solved in this thesis are advection and diffusion, which aided by the Fourier transform, can be rewritten as a set of ordinary differential equations (ODE). These ODEs can then be integrated in time with a Runge-Kutta method.Detta kandidatarbete går ut på att betrakta tre olika diskreta fouriertransformer och jämföra deras beräkningstid. Fouriertransformen används sedan också för att lösa partiella differentialekvationer (PDE). Fouriertransformerna som betraktas kan ses som en matrismultiplikation. Denna matrismultiplikation visar sig har trevliga egenskaper. Nämligen att matrisen är välkonditionerad och att matrisinversen element liknar ursprungsmatrisens element, vilket kommer underlätta implementationen. Matrisen kan dessutom skrivas om genom diverse samband hos komplexa tal för att få snabbare beräkningstid. PDE:na som betraktas i detta kandiatarbete är advektions och diffusions, vilket med speciella antaganden kan skrivas om till en ordinär differentialekvation som löses med en Runge-Kutta metod. Fouriertransformen används för att derivera, då det motsvarar en multiplikation. Det visar sig att alla metoder har fördelar och nackdelar. Ena metoden gör beräkningen snabbare men kan endast använda sig av datamängder av viss storlek. Andra metoden kräver ett specifikt bibliotek för att fungera men är mycket snabbare än de andra två.