Proseminar im WS 2004/2005:

Fast Fourier Transform

und Verallgemeinerungen

Dozent	:	Prof. R. Hiptmair
Ort	:	HG F 26.3
Zeit	:	Mo 13:15-15:00
beginnt am	:	8.11.2004
2. Vorbesprechung	:	Mo 25.10.2004, 13:15, HG G 26.3
Kontaktperson	:	R. Hiptmair, hiptmair@sam.math.ethz.ch, K. Schmidt, schmidt@sam.math.ethz.ch
Voraussetzungen	:	Kenntnisse in Analysis und linearer Algebra, wie sie in den ersten zwei Semestern eines Mathematikstudiums erworben werden.

Beschreibung:

Die Grundaufgabe der trigonometrischen Interpolation lautet: Zu gegebenen $N$ Knoten $x_{j}\in[0,2\pi[$ und Stützwerten $z_{j}\in\mathbb{C}$, $j=0,\ldots,N-1$, finde ein trigonometrisches Polynom

$$p(x) = \sum\limits_{k=0}^{N-1} c_{k}\exp(ikx)\;,\quad c_{k}\in\mathbb{C}\;,$$ (1)

so dass

$$p(x_{j}) = z_{j}\;\,, j=0,\ldots,N-1\;.$$

Die dazu inverse Aufgabe ist die Auswertung eines trigonometrischen Polynoms (1): Zu gegebenen Koeffizienten $c_{k}\in\mathbb{C}$, $k=0,\ldots,N-1$ und Auswertungspunkten $x_{j}$, $j=0,\ldots,N-1$, finde die Werte von $p$ aus (1) an den Stellen $x_{j}$.

Naive Algorithmen für diese Aufgabenstellungen benötigen einen Rechenaufwand von der Ordnung $O(N^{2})$. Falls jedoch $x_{j} = \frac{2\pi j}{N}$, dann handelt es sich um eine sogenannte diskrete Fouriertransformation (DFT) und es lässt sich die Fast Fourier Transform (FFT) anwenden, deren Rechenaufwand nur $O(N\log N)$beträgt.

Leider lassen sich die FFT und ihre Varianten nicht auf den Fall beliebig verteilter Stützpunkte verallgemeinern. Deshalb wurden Verfahren entwickelt, die die oben genannten Aufgabenstellungen mit einem Rechenaufwand von weniger als $O(N^{2})$ approximativ lösen, das heisst, die $c_{k}$ bzw. $p(x_{j})$ werden nur näherungsweise berechnet. Diese Verfahren sind unter dem Kürzel NFFT (non-equispaces fast Fourier transform) bekannt.

Die Artikel [7,18,13] verschaffen einen guten Überblick über die Thematik. Für ein tieferes Studium von Varianten der klassischen FFT sind [6,17] empfohlen. Softwre für NFFT findet man unter http://www.math.mu-luebeck.de/potts/nfft/.

Vorträge:

Im Rahmen des Seminars sollen bis zu 10 Vorträge gehalten werden, die den Inhalt von Originalarbeiten bzw. Übersichtsartikeln referieren.

• Die Vorträge sollen insgesamt ca. 60-75 Minuten dauern und eine Pause von ca. 15 Minuten kann eingeplant werden.
• Die Vorträge sollen mit Hilfe von Laptop und Datenprojektor gehalten werden.
  LaTeX-Präsentationsfolien lassen sich mit der Software Prosper bequem erzeugen.

1. Primfaktor-FFT [16], Vortragender Giovanni Morosoli, 15.11.2004
2. Chirp-z-FFT [2], Vortragender, Michael Blaser, 22.11.2004
   
3. Schnelle nichtäquidistante diskrete Fourier-Transformation II [3], Vortragender Erich Carelli, 6.12.2004
   
4. Schnelle nichtäquidistante diskrete Fourier-Transformation III [8], nicht vergeben
   
5. Schnelle nichtäquidistante diskrete Fourier-Transformation IV [14], Julian Sagredo,13.12.2004
   
6. Schnelle nichtäquidistante diskrete Fourier-Transformation IV [9][1] [4,5], Zusammenfassung von R. Hiptmair, 20.12.2004
   
7. Inverse NFFT [11], Vortragender Jan Kayatz, 10.01.2005
   
8. Schnelle NFFT-basierte Summation [12], Patrick Meury, 24.01.2005