Algorithm - Fast Fourier Transformation (FFT) (time to frequency and vice versa)

Sorting Quicksort Anim


A fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier transform (DFT) and its inverse.

Fourier analysis converts:

  • time (or space) - of period P
  • to frequency (or wavenumber) - of value 1/P

and vice versa

Time Domain To Frequency Domain

An FFT rapidly computes such transformations by factorizing the discrete Fourier transform (DFT) matrix into a product of sparse (mostly zero) factors.

In 1994 Gilbert Strang described the fast Fourier transform as “the most important numerical algorithm of our lifetime” and it was included in Top 10 Algorithms of 20th Century by the IEEE journal Computing in Science & Engineering.

Documentation / Reference

Discover More
Sorting Quicksort Anim

An is a (procedure|method) for solving a problem. If there exists an algorithm, the function that performs it is called computable. Study of algorithms dates at least to Euclid and were formalized by...
Card Puncher Data Processing
Linear Algebra - (Dot|Scalar|Inner) Product of two vectors

A dot Product is the multiplication of two two equal-length sequences of numbers (usually coordinate vectors) that produce a scalar (single number) Dot-product is also known as: scalar product or...
Time Serie - Seasonality (Cycle detection)

Seasonality is a cycle in time serie. The season is used a discreet regression variable and code it as dummy variables). For instance: 1 if it's the season 0 if it's not the season If you...

Share this page:
Follow us:
Task Runner