Schnelle Fourier-Transformationen für nichtäquidistante Daten und Anwendungen

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 𝓞(N^2d) auf 𝓞(N^d log N). 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 äquidistante 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 𝓞(N^d log N + m ^dN) , wobei m nur von der geforderten Exaktheit des Ergebnisses abhängt.

Auf dieser Grundlage entwickeln wir schnelle Summationsalgorithmen der Form an den Knoten y_j,x_k ∈ ℝ^d, wobei K radial-symmetrische Kerne der Form K(x) = K(||x||₂) sind. Diese schnellen Algorithmen können zur Interpolation mitradialen 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