Реализация двумерного массива FFT

Question

В настоящее время я использую некоторый код C для отображения эволюции решений уравнения 1D Шредингера с использованием метода Фурье.

Этот метод использует алгоритм FFT из числовых рецептов в C для вычисления второй производной (в k пробеле) в уравнении из значений функций в массиве 1D столбцов как часть процесса.

Я хотел бы перейти к 2D-решениям, которые, как я полагаю, потребуют «сетку» 2D-массива для значений функции в этих точках.

Мои вопросы таковы:

Могу ли я реализовать этот же FFT на массив NxN? Если да, то как?

Нужен ли мне другой алгоритм БПФ?

Спасибо.

Исходный код, я использую для БПФ:

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

Поскольку код 1D FFT готовы, вы можете построить 2D FFT методом Row-Column, т.е. первым выполнить 1D FFT на каждой строке, затем выполните 1D БПФ в каждом столбце или сначала выполните 1D БПФ на каждом столбце, затем выполните 1D БПФ в каждой строке. Этот подход основан на сепарабельном свойстве 2D FFT. Обратите внимание, что 1D БПФ являются обработкой на месте, то есть данные для первых 1D БПФ могут быть реальным типом, но стали сложным типом для второго этапа.