Slow Fourier Transforms

Consider a general 1D Fourier transform relating two vectors of length $n$:

• $\{ x_k; 0 \leq k < n \}$ contains the values in real-space
• $\{ X_k; 0 \leq k < n \}$ contains the frequency components
  
  $$X_k = \sum_{j=0}^{n-1} \exp( -2 \pi {\rm i} k j / n) x_j$$
  
  
  This is just a matrix-vector multiplication $X_k = F_{kj} x_j$
• $F_{k j} = \left[ \exp( -2 \pi {\rm i} / n) \right]^{k j} = \omega_n^{k j}$
• A straightforward implementation requires ${\cal O}(n^2)$ operations.