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

Question

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

有什么建议/参考吗？

Answer 1

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

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

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

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

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

• 带有 MapReduce 的 Schönhage-Strassen 算法用于乘以 T 比特整数
• 使用 MapReduce 进行 FFT