Not logged in.

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Multipoint Incremental Fourier Transformation
Organization Unit
Authors
  • Dimitri Degkwitz
Supervisors
  • Muhammad Saad
  • Michael Hanspeter Böhlen
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2021
Abstract Text In radio astronomy the discrete Fourier Transformation is crucial for evaluating telescope data. An increased interest in a streaming approach to the Fourier Transformation has led to the development of the Single Point Incremental Fourier Transformation (SPIFT), by Saad et al. SPIFT only handles one datapoint at a time. We developed two new algorithms which evaluate data points in batches. The first algorithm groups datapoints with similar characteristics into a dictionary before SPIFT is applied. The main focus of this report is on the second algorithm, that uses dictionaries and an algorithm we named Doublestep. Doublestep uses symmetries in SPIFT to reduce the necessary number of complex additions. In theory MPIFT with dictionaries and Doublestep reduces the asymptotic complexity of SPIFT by O(N/log(N)) for batches of smaller sizes. Our implementations confirmed that they reduced the complexity significantly.
Zusammenfassung In der Radioastronomie spielt die Diskrete Fourier Transformation eine zentrale Rolle bei der Auswertung von Teleskopdaten. Ein erhöhtes Interesse an kontinuierlichen Auswertungen der Daten führte Saad et al. dazu, den Single Point Incremental Fourier Transformation (SPIFT) Algorithmus zu entwickeln. SPIFT wertet Datenpunkte einzeln aus. Wir entwickelten zwei neue Algorithmen zur Auswertung von Datenpünkten in Bündeln. Der erste gruppiert Datenpunkte zuerst basierend auf gemeinsamen Charakteristika in Zuordnungstabellen, bevor SPIFT durchgeführt wird. Der Fokus dieser Arbeit ist auf dem zweiten Algorithmus, der neben Zuordnungstabellen auch einen von uns entiwckelten Algorithmus den wir Doublestep genannt haben, benutzt. Doublestep nutzt Symetrien in SPIFT um die notwendige Anzahl komplexen Additionen zu reduzieren. Theoretisch reduziert Doublestep die asymptotische Komplexität um O(N/log(N)) für kleinere Bündel. Unsere Implementationen haben bestätigt, dass sie die Laufzeit siginifikant reduzieren.
PDF File Download
Export BibTeX