Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


41. Die schnelle Fourier-Transformation



Berechnung in den Einheitswurzeln

Das Kernstück unserer Implementation ist eine Prozedur für die Berechnung eines Polynoms vom Grad N - 1 für die N-ten Einheitswurzeln. Das heißt, daß diese Prozedur die N Koeffizienten, die das Polynom definieren, in die N Werte transformiert, die sich aus der Berechnung dieses Polynoms für alle N-ten Einheitswurzeln ergeben.

Es mag den Anschein haben, daß dies nicht genau das ist, was wir benötigen, da wir als ersten Schritt der Prozedur für die Polynom-Multiplikation Polynome vom Grad N - 1 in 2N - 1 Punkten berechnen müssen. In Wirklichkeit ist das aber kein Problem, da wir ein Polynom vom Grad N - 1 als Polynom vom Grad 2N - 2 betrachten können, bei dem N - 1 Koeffizienten (die Koeffizienten der Glieder mit dem höchsten Grad) den Wert null haben.

Der Algorithmus, den wir zur gleichzeitigen Berechnung eines Polynoms vom Grad N - 1 in N Punkten benutzen werden, beruht auf einer einfachen Strategie vom Typ »Teile und Herrsche«. Anstatt die Polynome in der Mitte zu teilen (wie in dem in Kapitel 4 angegebenen Algorithmus für die Multiplikation), zerlegen wir sie in zwei Teile, indem wir ihre Glieder abwechselnd in diese Teile aufnehmen. Diese Zerlegung kann leicht mit Hilfe von Polynomen mit einer halb so großen Anzahl von Koeffizienten ausgedrückt werden. Zum Beispiel werden für N = 8 die Glieder wie folgt umgeordnet:

p(x) = p0 + p1x + p2x2 + p3x3 + p4x4 + p5x5 + p6x6 + p7x7
= (p0 + p2x2 + p4x4 + p6x6) + x(p1 + p3x2 + p5x4 + p7x6)
== pe(x2) + xpo(x2).

Die N-ten Einheitswurzeln sind für diese Zerlegung geeignet, da man bei Quadrierung einer Einheitswurzel eine andere Einheitswurzel erhält. Tatsächlich gilt sogar noch mehr: Wenn man eine N-te Einheitswurzel quadriert, erhält man für gerades N eine 1/2 N-te Einheitswurzel (eine Zahl, deren 1/2 N-te Potenz den Wert 1 hat). Dies ist genau das, was benötigt wird, damit die »Teile und Herrsche«-Methode angewandt werden kann. Um ein Polynom mit N Koeffizienten in N Punkten zu berechnen, zerlegen wir es in zwei Polynome mit 1/2 N Koeffizienten. Diese Polynome brauchen nur in 1/2 N Punkten (den 1/2 N-ten Einheitswurzeln) berechnet zu werden, um die Werte zu ermitteln, die für die vollständige Berechnung benötigt werden.

Um dies zu veranschaulichen, betrachten wir die Berechnung eines Polynoms p(x) vom Grad 7 für die achten Einheitswurzeln

W8: w80, w81, w82, w83, w84, w85, w86, w87.

Da w84=-1 gilt, ist dies das gleiche wie die Folge

W8: w80, w81, w82, w83, -w80, -w81, -w82, -w83.

Wenn man jedes Glied dieser Folge quadriert, erhält man zwei Kopien der Folge {W4} der vierten Einheitswurzeln:

w82: w40, w41, w42, w43, w40, w41, w42, w43.

Unsere Gleichung

p(x) = pe(x2) + xpo(x2)

gibt nun sofort an, wie p(x) für die achten Einheitswurzeln aus diesen Folgen berechnet werden kann. Zuerst berechnen wir pe(x) und po(x) für die vierten Einheitswurzeln. Dann setzen wir in der obigen Gleichung für x jede der achten Einheitswurzeln ein, wozu es erforderlich ist, den entsprechenden Wert von pe zu dem Produkt des entsprechenden Wertes von po mit der achten Einheitswurzel zu addieren:

p(w80) = pe(w40) + w80po(w40),
p(w81) = pe(w41) + w81po(w41),
p(w82) = pe(w42) + w82po(w42),
p(w83) = pe(w43) + w83po(w43),
p(w84) = pe(w40) - w80po(w40),
p(w85) = pe(w41) - w81po(w41),
p(w86) = pe(w42) - w82po(w42),
p(w87) = pe(w43) - w83po(w43).

Im allgemeinen berechnen wir zur Bestimmung von p(x) für die N-ten Einheitswurzeln rekursiv pe(x) und po(x) für die N-ten Einheitswurzeln und führen die N Multiplikationen wie oben aus. Dies ist nur möglich, wenn N gerade ist, weshalb wir von jetzt an voraussetzen, daß N eine Zweierpotenz ist, so daß N während der gesamten Rekursion gerade bleibt. Die Rekursion bricht ab, wenn N = 2 ist, und po + p1x für 1 und -1 (die beiden »zweiten« Einheitswurzeln) mit den Ergebnissen p0 + p1 und p0 - p1 zu berechnen ist.

Eigenschaft 41.1 Ein Polynom vom Grad N - 1 kann in den N-ten Einheitswurzeln mit ungefähr N lg N Multiplikationen berechnet werden.

Die Anzahl der auszuführenden Multiplikationen genügt der fundamentalen rekurrenten Beziehung für das »Teile und Herrsche«-Prinzip M(N) = 2M(N/2) + N, die die Lösung M(N) = N lg N besitzt (Formel 4 in Kapitel 6). Das ist eine wesentliche Verbesserung gegenüber der einfachen Interpolationsmethode mit N2 Multiplikationen, doch natürlich ist dieses Verfahren nur für die Einheitswurzeln geeignet. w.z.b.w.

Hieraus ergibt sich ein Verfahren für die Umwandlung eines Polynoms aus seiner üblichen Darstellung mit N Koeffizienten in seine Darstellung mit Hilfe seiner Werte für die Einheitswurzeln. Diese Umwandlung des Polynoms aus der ersten Darstellungsform in die zweite ist die Fourier-Transformation, und die beschriebene effiziente Prozedur zur rekursiven Berechnung wird die »schnelle« Fourier-Transformation (fast Fourier transform, FFT) genannt. (Die gleichen Verfahren lassen sich auf allgemeinere Funktionen als Polynome anwenden. Genauer gesagt führen wir dann die »diskrete« Fourier-Transformation aus.)


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]