用MapReduce实现快速傅里叶变换算法

Question

我想实现一个快速傅立叶变换算法与MapReduce。我知道一个递归FFT算法，但我需要你的指导方针，以便使用Map/Reduce方法来实现它。

任何建议/参考？

Answer 1

我们可以用一些定理将问题分解为子问题的基本思想。

在傅立叶Transfom的情况下，问题是FT的标准定义：

与展望未来：

应用Cooley–Tukey FFT algorithm我们可以把它分成两个子问题后转换，理论上它可以用并行编程来解决。

也许，你会发现下面的链接有用：

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