Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Implementation and Performance Evaluation of multi dimensional Fast Fourier Transform Algorithms on Streaming Data using Apache Flink
Organization Unit
Authors
  • Claudio Brasser
Supervisors
  • Michael Hanspeter Böhlen
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2018
Abstract Text In this thesis, different versions of the Fast Fourier Transform algorithm are implemented in order to evaluate their performance in a streaming environment. For this purpose, we built a streaming pipeline for the sampled input data. The dataset origins from the domain of radio astronomy where the Fourier Transform is a commonly used algorithm in the process of computing images from raw data. Cooley-Tukey FFT algorithms are a subset of FFT algorithms that use a divide-and-conquer approach to improve the runtime complexity. The discussed variations of the Cooley-Tukey FFT algorithm are Radix-2, Radix-4, and Split Radix. For each algorithm its explicit definition in the pseudo-code language, the corresponding mathematical equations, as well as a butterfly flow diagram is presented. The Split-Radix FFT algorithm performed best across all algorithms and parameter settings followed by Radix-4 and Radix-2.
Zusammenfassung In dieser Arbeit werden verschiedene Versionen der schnellen Fourier Transformation (FFT) implementiert, um deren Laufzeit auf streaming Daten zu evaluieren. Zu diesem Zweck haben wir eine streaming Applikation für Messdaten entwickelt. Die Daten stammen aus dem Bereich der Radio-Astronomie, wo die Fourier Transformation oft verwendet wird, um Bilder aus Rohdaten zu berechnen. Cooley-Tukey FFT Algorithmen sind eine Teilgruppe von FFT Algorithmen, welche ein 'divide-and-conquer' Verfahren benutzen und somit eine verbesserte Laufzeitkomplexität erreichen. In dieser Arbeit werden Radix-2, Radix-4 und Split-Radix Implementationen untersucht. Der Split-Radix Algorithmus stellte sich als die effizienteste unserer Implementationen heraus, unabhängig von anderen Parametern der Applikation.
PDF File Download
Export BibTeX