FFT二维数组的实现

Question

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

作为过程的一部分，此方法使用 C 中数值食谱中的 FFT 算法从一维列数组中的函数值计算方程中的二阶导数（在 k space 中）。

我想进入二维解决方案，我想这需要一个二维数组 'grid' 作为函数在这些点的值。

我的问题是：

我还能在 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在每一列上，然后在每一行上执行 1D FFT。这种方法基于 2D FFT 的可分离属性。请注意，一维 FFT 是就地处理，即前一维 FFT 的数据可能是实数类型，但在第二阶段已变为复数类型。

FFT二维数组的实现

Implementation of FFT 2D array

c

2d

fft