Fast Fourier Transformation Algorithmus Implementierung mit MapReduce

Question

Ich möchte einen Fast Fourier Transformation Algorithmus mit MapReduce implementieren. Ich kenne einen rekursiven FFT-Algorithmus, aber ich brauche Ihre Richtlinie, um sie mithilfe eines Map/Reduce-Ansatzes zu implementieren.

Irgendwelche Vorschläge/Referenzen?

Answer 1

Die Grundidee, dass wir einige Theoreme verwenden können, um das Problem in Teilprobleme zu unterteilen.

Bei Fourier Transfom, Problem ist, Standard-Definition von FT:

Nach Cooley–Tukey FFT algorithm wenden wir es auf zwei Teilprobleme aufteilen:

vorwärts bewegen mit, dass Transfomation, theoretisch könnte es mit paralleler Programmierung gelöst werden.

Vielleicht werden Sie folgende Links hilfreich:

• Schönhage-Strassen Algorithm with MapReduce for Multiplying Terabit Integers
• FFT with MapReduce