关于CUFFT输入大小

Question

CUFFT库支持的算法可以用2^a、X3、bX5、cX7、d等形式进行优化。

他们怎么能做到这一点？

据我所知，FFT只能为2^a输入大小提供最佳性能。

Answer 1

这意味着，素数因子大于7的输入大小会变慢。

Answer 2

Cooley算法可以对各种不同的DFT长度进行运算，可以表示为N= N_1*N_2，该算法将长度N的DFT递归表示为长度为N_2的较小的DFT。

正如您注意到的，最快的通常是基-2因式分解，它递归地将长度N的DFT分解为长度N/2的2个较小的DFT，运行在O(NlogN)中。

然而，实际性能将取决于硬件和实现。例如，如果我们考虑线程翘曲大小为32的cuFFT，那么长度为32的DFT将是最优的(注意:仅举一个例子，我不知道cuFFT下存在的实际优化)。

简单回答:基于Cooley-Tukey基-n算法，对任意素数分解的基础代码进行了优化，最多可达7。

http://mathworld.wolfram.com/FastFourierTransform.html

algorithm