 The DFT is obtained by decomposing a sequence of values into components of different frequencies.This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical.An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors.