algorithm - FFT 有多少 FLOPS？

Question

我想知道快速傅里叶变换 (FFT) 执行了多少 FLOPS。

所以，如果我有一个 1 维数组，包含 N 个 float ，我想计算这组数字的 FFT，有多少 FLOPS 需要执行吗？

我知道这取决于所使用的算法，但最快的可用算法呢？

我也知道 FFT 的缩放比例为 N*log(N) 但这不会回答我的问题。

Answer 1

这取决于实现。最快不一定意味着最低的 FLOP 或最高的 FLOPS。速度通常是通过利用HW 架构而不是降低FLOP 来实现的。那里有太多的实现，所以没有实际代码和架构的问题是无法回答的。

我喜欢预先计算的 W 矩阵实现，因为我通常对单一分辨率矩阵使用 FFT 多次，因此无需多次计算 W每个决议。这可以显着减少每个递归层的FLOP。

例如这个DFFTcc每次迭代有 14 个 FLOP，仅使用 +,-,* 操作。假设 1D FFT 情况 N=8 并在我没有犯任何愚蠢错误的情况下使用基本数据类型:

FLOP = 8*14 + (4+4)*14 +(2+2+2+2+2)*14 +(1+1+1+1+1+1+1+1)*2 = 14*N*log2(N) + 2*N = 352

如果您使用真实输入/输出，您甚至可以降低第一个/最后一个递归层的输入/输出。但是简单的 FLOP 计数是不够的，因为有些操作比其他操作更复杂。而且 FLOP 并不是影响速度的唯一因素。

现在要获得 FLOPS，只需测量 time [s] FFT 所花费的时间:

FLOPS = FLOP/time