MATLAB：寻找离散傅立叶变换的更快方法

Question

我正在尝试在 matlab 中编写代码，其功能与内置 fft 函数基本相同。因此计算任何给定输入向量的离散傅立叶变换。

变换由

给出

%                    N
%      X(k) =       sum  x(n)*exp(-j*2*pi*(k-1)*(n-1)/N), 1 <= k <= N.
%                   n=1

现在我创建了自己的代码来执行此操作，但是当我查看计算时间时，计算量大约是 200 倍。显然我想减少这个。

在我的代码的计算部分下方，其中 y 是输出向量。

N=length(input_vector)

for k = 1:N
        y(k)=0;
        for n = 1:N
            term = input_vector(n)*exp(-2*pi*1i*(n-1)*(k-1)/N);
            y(k)=y(k)+term;
        end
end

现在我认为计算量很大，因为 for 循环和 y(k)=y(k)+term 行，因为这在所有迭代中都会发生。我想我应该能够通过使用 vector/matrix 符号或使用带有虚拟变量的函数然后迭代这些函数来使它更小。但我不知道如何开始这个过程。

如有任何帮助或建议，我们将不胜感激。

Answer 1

使用implicit expansion可以大大减少算法的计算时间：

% Vector length
N = length(input_vector);

% Vectorized DFT algorithm
y = sum(input_vector.*exp(-2*pi*1i*[0:N-1].'*[0:N-1]/N),2);

但是有两个缺点：

向量化会消耗大量内存（因为向量 N*N 必须创建）
它不会比内置函数更快。

MATLAB：寻找离散傅立叶变换的更快方法

MATLAB: Faster method of finding Discrete Fourier Transform

time

matlab

matrix-multiplication