Fast Fourier transformation computes discrete Fourier transformation efficiently. It is used in many areas including fast polynomial multiplication, signal processing and computing sequence convolutions efficiently.

Fast Fourier Transformation

An algorithm used to compute discrete Fourier transformation. Used mainly in signal processing to convert signals into frequency domain.

One application of FFT in problem solving is to compute fast polynomial multiplication where it turns into a point-wise multiplication on the transformed sequences. Mainly it is used to compute convolutions of two sequences and to solve linear recurrences efficiently.

The algorithm is a divide and conquer approach over complex numbers.