c - FFT 2D 数组的实现

Question

我当前正在使用一些 C 代码来使用傅立叶方法显示一维薛定谔方程的解的演变。

作为该过程的一部分，此方法使用 C 语言数值配方中的 FFT 算法根据一维列数组中的函数值计算方程中的二阶导数(在 k 空间中)。

我想转向 2D 解决方案，我想这需要一个 2D 数组“网格”来存储这些点处的函数值。

我的问题是:

我仍然可以在 NxN 阵列上实现相同的 FFT 吗？如果是这样，怎么办？

我需要不同的 FFT 算法吗？

谢谢。

我用于 FFT 的源代码是:

void four1(double data[], int nn, int isign)
{
    int n, mmax, m, j, istep, i;
    double wtemp, wr, wpr, wpi, wi, theta;
    double tempr, tempi;

    n = nn << 1;
    j = 1;
    for (i = 1; i < n; i += 2) {
    if (j > i) {
        tempr = data[j];     data[j] = data[i];     data[i] = tempr;
        tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
    }
    m = n >> 1;
    while (m >= 2 && j > m) {
        j -= m;
        m >>= 1;
    }
    j += m;
    }
    mmax = 2;
    while (n > mmax) {
    istep = 2*mmax;
    theta = TWOPI/(isign*mmax);
    wtemp = sin(0.5*theta);
    wpr = -2.0*wtemp*wtemp;
    wpi = sin(theta);
    wr = 1.0;
    wi = 0.0;
    for (m = 1; m < mmax; m += 2) {
        for (i = m; i <= n; i += istep) {
        j =i + mmax;
        tempr = wr*data[j]   - wi*data[j+1];
        tempi = wr*data[j+1] + wi*data[j];
        data[j]   = data[i]   - tempr;
        data[j+1] = data[i+1] - tempi;
        data[i] += tempr;
        data[i+1] += tempi;
        }
        wr = (wtemp = wr)*wpr - wi*wpi + wr;
        wi = wi*wpr + wtemp*wpi + wi;
    }
    mmax = istep;
    }
}

Answer 1

既然一维FFT代码已经准备好了，那么就可以通过行列法构建二维FFT，即先对每一行进行一维FFT，然后对每一列进行一维FFT，或者先对每一行进行一维FFT然后对每一行执行一维 FFT。该方法基于 2D FFT 的可分离特性。请注意，一维 FFT 是就地处理，即前一维 FFT 的数据可能是实数类型，但第二阶段已变成复数类型。