使用NAG函数加速Matlab DFT

Question

我想将一些Matlab傅立叶变换命令FFT和IFFT转换为NAG函数。DFT是：

• fft(A,n)

• fft(A,n,dim)

• ifft(A,[],dim)

其中A是复向量。例如，fft(A,n)是c06fc(real(A),imag(A),'n',n)。

问题：我很难找到与fft(A,n,dim)和ifft(A,[],dim)执行相同任务的适当NAG函数。

上下文：我使用Bruno Luong的卷积函数convnfft来计算具有100万个复数元素的向量的卷积，convnfft(A,B,'same')。Luong的函数使用FFT来快速计算卷积，我想通过使用NAG函数来加快速度。

Answer 1

少数备注：

1. MATLAB使用FFTW进行DFT(请参见MATLABfftw())
   FFTW被认为是最快的FFT库。我真的怀疑NAG的实施速度是否更快。你不会得到比MATLAB更快的FFT
2. 我看到你在频域中使用乘法来应用时域中的卷积。我只想指出，这并不总是更快的事情。这实际上取决于滤波器的长度与信号的长度。如果过滤器很短，你最好在时域中进行

一维卷积时域与傅立叶域的复杂性

假设滤波器的长度为m，而信号的长度为n(假设n>m)
则Tome域卷积的复杂度为O(mn)
然而，要在傅立叶域中应用卷积，必须使滤波器和信号具有相同的长度，然后复杂度为O(2nlog(n))
因此，对于2log(n)>m的情况，最好使用时域卷积。

由于这是实践中的渐近分析，因此需要2log(n)>>m才能在时域卷积上具有实际增益。