Is $O (N \log N)$ FFT speed the fastest we can ever attain?

I am wondering about whether or not there is a theoretical limit as to the speed at which we can compute a DFT. We all know that the FFT executes in $O (N \log N)$ time. However, is this a lower bound of some sort?

Might there be yet faster algorithms that have yet to be discovered which we do not currently know about that are faster, or is this a holy boundary that cannot be crossed?

Edit: Apparently this is a known unsolved problem in CS, (thanks to @John).

So, what are the details of the problem? Where would one start to try to make improvements?

• Wikipedia has that on the list of unsolved problems in computer science: en.wikipedia.org/wiki/… – John Jan 17 '14 at 14:16
• @John Thanks - does this mean that they know it can be lowered, (but do not know to what value), or does this mean that that they are not even sure if it can even be lowered? – TheGrapeBeyond Jan 17 '14 at 14:20
• Both. The lower bound is not known. – John Jan 17 '14 at 14:37
• @John I updated the question, thanks for your feedback. – TheGrapeBeyond Jan 17 '14 at 14:51
• there's something called the Winograd fourier transform that was supposed to be $O(N)$. – robert bristow-johnson Jan 17 '14 at 15:42

2 Answers

While the general problem remains an open problem in theoretical computer science, there are (randomized) algorithms known as sparse fast fourier transforms which can approximate DFTs to a certain approximation factor when there are only a few DFT coefficients you are concerned with.

You can find some details in these papers and related papers (downloadable here):

• Hassanieh, Haitham, et al. "Nearly optimal sparse Fourier transform." Proceedings of the 44th symposium on Theory of Computing. ACM, 2012.

• Hassanieh, Haitham, et al. "Simple and practical algorithm for sparse Fourier transform." Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2012.

Most of the "divide and conquer" algorithm in computational paradigm uses O(NlogN) as the lower bound. It provides some sort of balance between space and time complexity. Sort is one of the application for divide and conquer approach. FFT has also been computed using the same "Divide and Conquer" approach.

O(N) algorithms require more space (memory) for computation although it is fast. The only way to make improvement is to improve the speed of the multiplication using different algorithms like karatsuba multiplication, Vedic multiplication, etc.

• Vedic multiplication? Good grief, that has been thoroughly debunked a long time ago. – Dilip Sarwate Jan 19 '14 at 3:25
• Karatsuba is worse than O(N*log(N)), check your sources. – LutzL Jan 29 '14 at 16:10