Fast Fourier Transforms FFT

The key reason for the FFT is the reduction of $n^2$ required calculations to $\frac{1}{2}n\log n$. The common $n\times n$ Fourier matrix $F$ is given as

$$F=\underset{\text{Count columns and rows from 0 to (n−1)}}{\underbrace{\left[\begin{array}{ccccc}1& 1& 1& \dots & 1\\ 1& w& w^2& \dots & w^{(n-1)}\\ 1& w^2& w^4& \dots & w^{2(n-1)}\\ ⋮& ⋮& ⋮& & ⋮\\ 1& w^{n-1}& w^{2(n-1)}& \dots & w^{(n-1{)}^2}\end{array}\right]}}$$

$w$ is the first one of the $n$ square roots of unity, $w^n=1$, $w=e^{2\pi /n}$. Counting columns and rows from $0$ to $(n-1)$ the it is easy to calculate the matrix’ entries with $a_{ij}=w^{ij}$.

Now, the Fast Fourier Transform takes this initial matrix $F$ that requires $n^2$ calculations to apply and reduces it to a combination of matrices. When $n=64$ we have $F\_64$. The FFT decomposition rewrites $F\_64$ as as combination of the smaller but connected Fourier matrix $F\_32$. (Because the set of n roots of unity are included in the sets that are the powers of n: root $w^4\in w^{4n}\text{with}n\ge 1$.)

$$F\_64=\underset{\text{Puts F64 back together}}{\underbrace{\left[\begin{array}{cc}I& D\\ I& -D\end{array}\right]}}\underset{\text{Decomposition}}{\underbrace{\left[\begin{array}{cc}F\_32& \\ & F\_32\end{array}\right]}}P$$

$P$ reorders components putting even before odd. $P\text{[}{x}_{1}x\_2x\_3x\_4\dots ]=\text{[}x\_0x\_2\dots x\_1x\_3\dots ]$. The decomposition of $F\_n$ is done recursively until $F\_2$ is reached yielding the optimal $\frac{1}{2}n\log n$ required calculations.