Fast Fourier transform: Derivation, implementation and application of the Cooley-Tukey fast Fourier transformShow others and affiliations
2025 (English)Independent thesis Basic level (degree of Bachelor), 13 HE credits
Student thesisAlternative title
Snabb Fouriertransform : Härledning, implementation och applikation av Cooley-Tukeys algoritm för snabb Fouriertransform (Swedish)
Abstract [en]
The fast Fourier transform (FFT) is an algorithm which transforms sampled data from state-space to Fourier-space. By approximating the continuos Fourier transform we first derive a naive discrete Fourier transform (DFT). This naive implementation transforms samples via a matrix product, and has a time complexity of $\mathcal{O}(n^2)$. The complexity can be lowered to $\mathcal{O}(n\log n)$ when the number of samples is a power of two, or padded to one. To do this, we decompose the DFT matrix into $\log_2 n$ products which can be calculated in linear time.
We compare the DFT and FFT algorithms and confirm that the asymptotic time complexity conforms with the theoretical result. We also compare recursive, iterative and multithreaded FFT variants and find that they performed similarly. The choice of programming language, however, has a big impact on performance. Finally, we compare our implementations to the state-of-the-art FFT library FFTW.
Two applications of the DFT are explored. The first, to numerically calculate matrix-vector products with circulant and Toeplitz matrices. The second, to filter coastline data.
The FFT algorithm, while theoretically complex, has relatively simple implementations that perform well compared to a naive DFT. An area that could be improved in our implementation is the handling of signal sizes that are not powers of two. However this is not a trivial problem to solve. Still, the algorithm can be used effectively in a wide range of applications.
Place, publisher, year, edition, pages
2025. , p. 29
Keywords [en]
FFT, DFT, Cooley-Tukey, Fourier transform
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-214587ISRN: LiTH-MAT-EX--2025/08--SEOAI: oai:DiVA.org:liu-214587DiVA, id: diva2:1966827
Subject / course
Computational Mathematics
Presentation
2025-05-28, S27, C-huset, Campus Valla, Linköpings universitet, Linköping, 13:15 (Swedish)
Supervisors
Examiners
2025-06-112025-06-102025-06-11Bibliographically approved