这比已证明的证据更多的是轶事证据，但似乎 FFT 的现有实现（例如FFTW）对其扩展能力有限制。

当我们开始使用 LAMMPS 时${\bf k}$- 超大型系统中的空间求解器（$O(10^7)$atom)，我们发现扩展仍在继续，只要我们能够将处理器的数量保持在足够小，以便它们可以放在一个机架上。一旦我们尝试进一步扩展（超过大约 4K 处理器，具体取决于机器），扩展就崩溃了——显然是因为在处理器之间推送数据的通信成本变得太大而无法维持扩展。[最近，为了规避这个问题，他们引入了将处理器分配的某个分区专用于 FFT 计算的能力。]

但这里的关键信息是 FFT 应该扩大规模。然而，当人们从对算法性能的理论考虑转变为在实际 HPC 平台上的实际实施时，有时会出现意想不到的限制和相互作用。

快速多极法 (FMM) 是$O(n)$并且具有低得多的通信要求，因此它提供了高度可扩展的离散傅里叶变换。Edelman、McCorquodale 和 Toledo (1999)未来的快速傅立叶变换？分析这种方法并得出结论，FMM 在大规模上比传统的 FFT 更可取。请注意，FMM 只是近似值，因此如果您需要非常高的精度，常数会更差。感谢 Jack Poulson 在上周的讨论中指出了这一点。

在偏微分方程的背景下，重要的是要认识到$n$对于所需的 1D FFT，通常会像$d$网格点总数的 th 根，其中维数$d$最常见的是 3。

在 Google Scholar 上搜索“并行 FFT”或“伪光谱可扩展性”会产生大量我没有资格评估的信息。但这似乎是最近可以在实践中完成的一个很好的例子：

用于流体湍流的可扩展并行伪光谱计算的混合 MPI-OpenMP 方案

抽象的：

提出了一种混合方案，该方案利用 MPI 进行分布式内存并行，而 OpenMP 用于共享内存并行。这项工作的动机是希望在新兴的千万亿级、高核心数、大规模并行处理系统上的流体湍流的伪光谱计算中实现异常高的雷诺数。混合实现源自并增强了经过充分测试的可扩展 MPI 并行伪光谱代码。混合范式为伪光谱网格的域分解带来了新的画面，这有助于理解全局数据的 3D 转置，这是并行快速傅立叶变换的核心组成部分。数值离散化。提供了混合实现的详细信息，和性能测试说明了该方法的实用性。结果表明，混合方案在高达约 20000 个计算内核的情况下实现了接近理想的可扩展性，最大平均效率为 83%。提供的数据演示了如何选择最佳数量的 MPI 进程和 OpenMP 线程，以优化两个不同平台上的代码性能。

如果您有无限数量的处理器，则可以确定 DFT$O(n)$时间。

在朴素算法中，您可以将每个输出点放在一个单独的节点上，并计算该傅立叶变换点$O(\log n)$时间。任何快速算法至少应该能够匹配这种缩放。

但是，您还需要将所有傅立叶变换点收集到一个数组中，这需要$O(n)$时间。