A
fast Fourier transform (
FFT)
algorithm computes the
discrete Fourier transform (DFT) of a sequence, or its inverse.
Fourier analysis converts a signal from its original domain (often time or space) to a representation in the
frequency domain and vice versa. An FFT rapidly computes such transformations by
factorizing the
DFT matrix into a product of
sparse (mostly zero) factors. As a result, it manages to reduce the
complexity of computing the DFT from
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!ARV6FUJ2JP&type=0&index=3832)
, which arises if one simply applies the definition of DFT, to
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!ARV6FUJ2JP&type=0&index=1311)
, where
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!ARV6FUJ2JP&type=0&index=3317)
is the data size.