4
$\begingroup$

Is it possible to make an algorithm faster than the fast Fourier transform to calculate the discrete Fourier transform (is there proofs for or against it)?

OR, a one that only approximates the discrete Fourier transform, but is faster than $O(NlogN)$ and still gives about reasonable results?

Additional requirements:

1) Let's leave the quantum computing out

2) I don't mean faster in sense of how its implemented for some specific hardware, but in the "Big-O notation sense", that it would ran e.g. in linear time.

Sorry for my english

  • 0
    Join the proposal: They raffle one there, when it goes beta :-)2012-11-20

1 Answers 1

1

There is an algorithm called sparse fast Fourier transform (sFFT), which is faster than FFT algorithms when the Fourier coefficients are sparse.

  • 0
    This appears to be partly the same that was pointed out by WimC (the paper he mentions could be found from the page you provided). I will accept your answer. Thanks also for WimC!2012-11-20