Fast Fourier transform

O(N logN) divide-and-conquer algorithm to calculate the discrete Fourier transforms
An example FFT algorithm structure, using a decomposition into half-size FFTs
A discrete Fourier analysis of a sum of cosine waves at 10, 20, 30, 40, and 50 Hz

Hexagonal fast Fourier transform (HFFT) aims at computing an efficient FFT for the hexagonally-sampled data by using a new addressing scheme for hexagonal grids, called Array Set Addressing (ASA).

In many applications, the input data for the DFT are purely real, in which case the outputs satisfy the symmetry

As defined in the multidimensional DFT article, the multidimensional DFT

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.