Numerischer Aufwand bei der Berechnung der Fourier-Koeffizienten

Die Summen, die in den Formeln (19.208) auftreten, kommen auch im Zusammenhang mit der diskreten FOURIER-Transformation, z.B. in der Elektrotechnik, in der Impuls- und vor allem in der Bildverarbeitung, vor. Dabei kann N sehr groß sein, so daß die betreffenden Summen äußerst rationell berechnet werden müssen, denn die Berechnung der N Näherungswerte (19.208) für die FOURIER-Koeffizienten erfordert etwa N² Additionen und Multiplikationen. Für den Spezialfall N=2^p läßt sich jedoch mit Hilfe der sogenannten Schnellen FOURIER-Transformation FFT (Fast FOURIER-Transformation) die Anzahl der Multiplikationen von N² = 2^2p auf pN = p2^p senken. Die Größenordnung dieser Reduzierung erkennt man an dem folgenden Zahlenbeispiel:

Dadurch sinkt der Rechenaufwand und damit auch die Rechenzeit so stark ab, daß für einige wichtige Anwendungsgebiete bereits der Einsatz kleinerer Computer ausreicht.
Die FFT nutzt die Eigenschaften der N-ten Einheitswurzel, d.h. der Lösungen der Gleichung , aus, um die Summanden in (19.208) sukzessiv zusammenzufassen.