---
jupytext:
  formats: ipynb,md:myst
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.14.4
kernelspec:
  display_name: Python 3 (ipykernel)
  language: python
  name: python3
---

```{code-cell}
:tags: [hide-cell]

import mmf_setup;mmf_setup.nbinit()
import logging;logging.getLogger('matplotlib').setLevel(logging.CRITICAL)
%matplotlib inline
import numpy as np, matplotlib.pyplot as plt
try: 
    from myst_nb import glue
except ImportError: 
    glue = None
```

(sec:FFT)=
Fast Fourier Transform
======================

Consider performing the discrete Fourier transform (DCT) $\tilde{f}_{m}$ of a periodic function
tabulated at $N$ equally spaced points $f_n = f(x_n)$:
\begin{gather*}
  \tilde{f}_{m} = \sum_{n} \underbrace{e^{-2\pi \I mn/N}}_{F_{mn} = [\mat{F}]_{mn}}f_n, \qquad
  m, n \in {0,1,\dots, N-1}.
\end{gather*}
Naïvely, this is simply matrix multiplication, which requires $O(N^2)$ operations.

The fast-Fourier transform (FFT)