Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Use this tag for questions related to the fast Fourier transform, an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components.

A fast Fourier transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components. Those components are individual sinusoidal oscillations at distinct frequencies each with its own amplitude and phase.

An FFT algorithm computes the discrete Fourier transform (DFT) of a sequence or its inverse (IFFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. A FFT computes such transformations rapidly by factoring the DFT matrix into a product of sparse matrices. As a result, a FFT reduces the complexity of computing the DFT from $O(n^2)$ if one applies the definition of the DFT to $O(n\log n)$ where $n$ is the data size.

Fast Fourier transforms are widely used for many applications in engineering, science, and mathematics.

history | excerpt history