2D FFT

原始题目：LeetGPU - 2D FFT

题目描述

计算存储在 GPU 上的复值信号的二维离散傅里叶变换（2D DFT）。给定形状为 $M \times N$ 的二维复输入信号，使用行列分解法计算其 2D DFT：先沿每行应用 1D DFT，再对结果的每列应用 1D DFT。所有值均为 32 位浮点数。

输入和输出以交织实部和虚部的格式存储在一维数组中（行优先）：元素 $x[m, n]$ 的实部在索引 $2 \cdot (m \cdot N + n)$ 处，虚部在索引 $2 \cdot (m \cdot N + n) + 1$ 处。

实现要求

• 不允许使用外部库。
• solve 函数签名必须保持不变。
• 最终结果必须存储在 spectrum 中。

示例

Input:  M=2, N=2
        Signal (实部): [[1,0],[0,0]], (虚部): [[0,0],[0,0]]
Output: Spectrum (实部): [[1,1],[1,1]], (虚部): [[0,0],[0,0]]

约束条件

• $1 \le M, N \le 4{,}096$。
• 信号值为 32 位浮点（实部和虚部）。
• 性能测试在 $M = N = 2{,}048$ 下进行。

解题思路

二维 FFT 分解为 $M + N$ 次一维 FFT。GPU 上高效的 1D FFT 通常使用 Cooley-Tukey 算法结合 Stockham 自排序变体来避免 bit-reversal 排列。共享内存可以缓存当前行/列的数据。cuFFT 库是基准参照，但手写实现可以练习 warp shuffle 和 bank-conflict 优化。欢迎在 GitHub Discussions 分享你的解法。