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?

[John]

I found out that the Matlab built in function for FFT is compiled source code which probably runs faster.

[Matt J]

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

[John]

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]

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.