How to efficiently implement algorithm similar to FFT?

Question

John 2013-3-9

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/66468-how-to-efficiently-implement-algorithm-similar-to-fft

I am implementing an algorithm similar to FFT. The only difference is that I'm using my own custom twiddle factors for the butterfly operation to combine smaller DFTs into larger DFTs which is implemented through multiplication of matrices.

However, I am not getting the same performance as the regular FFT built in function. Is it a function of how I'm writing my code?

3 个评论
显示 1更早的评论隐藏 1更早的评论

Matt J 2013-3-9

编辑：Matt J 2013-3-9

The builtin FFT is also probably multi-threaded, whereas yours would not be.

John 2013-3-9

I am trying to compare computational complexity between my algorithm and Matlab's algorithm. Despite the fact that Matlab's algorithm is much faster, the complexities appear the same. For example, for increasing sizes, they both have a computational complexity of O(n log n)

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2013-3-9

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/66468-how-to-efficiently-implement-algorithm-similar-to-fft#answer_78012

编辑：Matt J 2013-3-9

If you write your customized butterfly operations as sparse matrix multiplications (see the SPARSE command), you might be able to get the benefit of multi-threading, similar to the FFT command.