algorithm - 对实际输入数据进行高效二维 FFT？

Question

我目前正在使用 opencl 为实际输入数据实现二维 FFT(更具体地说是使用 FFT 的快速二维卷积，所以我只需要一些行为足够相似的东西来应用卷积)。二维 FFT 是在行上使用一维 FFT，然后在列上使用一维 FFT 实现的。

为了提高效率，我尝试使用具有真实输入的 FFT 的对称性，以便能够计算更小的 FFT。我发现我可以将两行合并为一行，使用第一行作为实部，第二行作为虚部，对结果行执行第一个 1D FFT，然后使用对称属性来构造单个 1D FFT 的结果从那行。所以我所做的基本上是以下内容:

令 f 和 g 为矩阵中的行。

1. 构造x = f + i * g
2. 转换得到 F(x) = F(f) + i * F(g)
3. 使用对称性从 F(x) 中提取 F(f) 和 F(g)

但是我不能将结果直接输入到第二个 1D FFT，因为在那种情况下我不会变换整个矩阵，而是变换两个子矩阵。然而，在转换之间提取数据意味着要么存储更多数据(n/2+1 条目需要在实际输入上表达 1D FFT 的结果)，要么组合索引 0< 处的元素 并将 n/2 索引到一个元素中(使用相同的技巧组合，因为两个数字都保证是真实的)并使用相同数量的存储但必须为此做一个特殊的案例在我的卷积中。

由于我尝试尽可能多地重复使用缓冲区(由于 gpu 上可用的 RAM 有限)，使用更多存储空间并不是一个好的解决方案。此外，我的算法无法处理不是 2 的幂/16 的倍数的矩阵大小(因内核而异)。我也宁愿避免引入特殊情况，因为那些会使我的内核更加复杂，从而影响效率(我已经难以最小化每个内核使用的寄存器数量)。

所以我的问题是，是否有解决此问题的优雅方法，即无需使用更多内存或某些元素的特殊情况即可工作的方法？

理想情况下，我希望能够执行整个 FFT 而无需在 FFT 中间拆分我的组合数据，但我不确定这是否可能。

Answer 1

嗯……我的两个引用是:

http://www.engineeringproductivitytools.com/stuff/T0001/PT10.HTMhttp://images.apple.com/acg/pdf/FFTapps_20090909.pdf

我认为采用“hermitian”数据结构，将 0 和 n/2 值打包到第一个元素中是可行的方法，因为正向/反向和 hermitian 结构会更好。

这样，您就有了 rUnWrap(FFT(n/2, Even(x) + i*Odd(x)))= rFFT(x)，并且 riFFT 可以在“hermitian”阵列上运行，产生对偶数和奇数数组，再次给出原始结构。

还可以进行其他采样，将原始数组分解为4 n/2xn/2 数组，以 (0,0),(0,1),(1,0),(1,1) 为根，然后使用最终基数 4 在末尾包裹起来通过...也许这对 GPU 内存更好...我不知道。

艾伦