Fast implementation of the Fourier transform algorithm using MapReduce

Question

I want to implement Fast Fourier Transform algorithm with MapReduce . I know the recursive FFT algorithm, but I need your guide to implement it using the Map / Reduce approach.

Any suggestions / links?

Answer 1

The main idea is that we can use some theorems to divide the problem into subtasks.

In the case of the Fourier transform, the problem is the standard definition of FT:

After applying the Coley-Tukey FFT algorithm, we can divide it into two subtasks:

Moving forward with this translation, theoretically this can be solved using parallel programming.

You may find the following useful links:

• Schönhage-Strassen algorithm with MapReduce for multi-user terabit integers
• FFT with MapReduce