Fast Fourier transform
Other generalizations

An O (n 5 / 2 log n) {\textstyle O(n^{5/2}\log n)} generalization to spherical harmonics on the sphere S with n nodes was described by Mohlenkamp, along with an algorithm conjectured (but not proven) to have O (n 2 log 2 (n)) {\textstyle O(n^{2}\log ^{2}(n))} complexity; Mohlenkamp also provides an implementation in the libftsh library. A spherical-harmonic algorithm with O (n 2 log n) {\textstyle O(n^{2}\log n)} complexity is described by Rokhlin and Tygert.

The fast folding algorithm is analogous to the FFT, except that it operates on a series of binned waveforms rather than a series of real or complex scalar values. Rotation (which in the FFT is multiplication by a complex phasor) is a circular shift of the component waveform.

Various groups have also published "FFT" algorithms for non-equispaced data, as reviewed in Potts et al. (2001). Such algorithms do not strictly compute the DFT (which is only defined for equispaced data), but rather some approximation thereof (a non-uniform discrete Fourier transform, or NDFT, which itself is often computed only approximately). More generally there are various other methods of spectral estimation.
startend:end_checker