How to efficiently implement algorithm similar to FFT?

1 次查看（过去 30 天）
John
John 2013-3-9
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更早的评论
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
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 个）

类别

在 Help Center 和 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