How to efficiently implement algorithm similar to FFT?

2013 3 9
1 个回答
回答已采纳
6 次查看（30 天）

0 个投票

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更早的评论

John
John 2013-3-9
I found out that the Matlab built in function for FFT is compiled source code which probably runs faster.
Matt J
Matt J 2013-3-9
编辑：Matt J 2013-3-9
The builtin FFT is also probably multi-threaded, whereas yours would not be.
John
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)

请先登录，再进行评论。

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

 采纳的回答

Matt J
Matt J 2013-3-9
编辑：Matt J 2013-3-9

0 个投票

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.

更多回答（0 个）

类别

在 帮助中心 和 File Exchange 中查找有关 Fourier Analysis and Filtering 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by