Fast Fourier Transform algorithm implementation with MapReduce

Question

I want to implement a Fast Fourier Transform algorithm with MapReduce. I know of a recursive-FFT algorithm but I need your guideline in order to implement it using a Map/Reduce approach.

Any suggestions/references?

Answer 1

The basic idea that we can use some theorems to divide problem into subproblems.

In case of Fourier Transfom, problem is standard definition of FT:

After applying Cooley–Tukey FFT algorithm we can split it to two subproblems:

Moving forward with that transfomation, theoretically it could be solved with parallel programming.

Maybe, you'll find following links useful:

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