使用MapReduce的快速傅立叶变换算法实现

Question

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

是否有任何建议/参考？

Answer 1

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

[对于傅立叶变换，问题是FT的标准定义：

应用Cooley–Tukey FFT algorithm之后，我们可以将其分为两个子问题：

<< [

继续进行这种转换，理论上可以通过并行编程来解决。

也许，您会发现以下链接有用：

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