[mturmon]

We disagree.

The big-O results of the paper are interesting and with more work could prove a starting point for improvements in very long FFTs. Why long? Because, for big-O asymptotics to kick in, you'll need large n.

But, the domain of applicability seems to be a niche. The "7 non-negligible coefficients" result you refer to is for 8x8 DCT's (as in JPEG). That's n = 8. There are optimized implementations for the small-n cases that will utterly dominate a big-O optimal algorithm like this. Compare Strassen's algorithm for matrix *.

Have you looked at the code complexity of the algorithm in the paper? There are several interlocking components (hash functions, rebinning) that have their own big-O optimality claims and, in some cases, randomization. Getting it all to work together efficiently, given cache issues, even for large n (say, 10^6) would be a serious engineering challenge. People have been working on optimizing data flow for FFT for decades now, and the state of the art is very advanced.

I agree, that the result is interesting in principle. Runtime is actually sub-linear in n, the sequence length.