Schnelle Fourier-Transformationen für nichtäquidistante Daten und Anwendungen
- Daniel Potts (Universität zu Lübeck, Institut für Mathematik, Germany)
Abstract
Die Entwicklung effizienter Algorithmen für häufig wiederkehrende
Grundaufgaben ist ein wesentliches Anliegen der Numerischen Mathematik.
Dabei gehört die schnelle
Fourier-Transformation (FFT) zu
den bekanntesten schnellen Algorithmen.
Die d-variaten FFT reduzieren die arithmetische Komplexität der
diskreten Fourier-Transformation
von 
auf
. Viele Verfahren sind erst durch die
Effizienz der FFT von
praktischem Interesse, so z.B. Polynom-,
Matrizen-, Matrix-Vektor-Multiplikationen, Invertierung
grosser strukturierter Matrizen oder trigonometrische Interpolation
auf feinen Gittern.
In einer Vielzahl von weiteren Anwendungen der FFT wird die Beschränkung auf
"aquidistante Gitter als Nachteil aufgeführt.
In diesem Vortrag stellen wir schnelle Algorithmen zur Berechnung der
Fourier-Transformation für nichtäquidistante Daten (NFFT)
vor.
Im Gegensatz zur FFT ist die NFFT ein approximativer Algorithmus,
d.h. der Nutzer kann bestimmen, mit welcher endlichen Genauigkeit das Ergebnis
berechnet werden soll. Die hier vorgeschlagene NFFT hat eine
arithmetische Komplexität von 
, wobei m
nur von der geforderten Exaktheit des Ergebnisses abhängt.
Auf dieser Grundlage entwickeln wir schnelle Summationsalgorithmen
der Form
an den Knoten
, wobei 
radial-symmetrische Kerne der Form 
sind. Diese schnellen Algorithmen können zur Interpolation mit
radialen Basisfunktionen oder zur numerischen Lösung von
Integralgleichungen eingesetzt werden.
Abschließend diskutieren wir Anwendungen der NFFT in der
Computertomographie und der
diskreten Fourier-Transformation auf der Sphäre.
