TABLE OF CONTENTS Once the [FFT] method was established it became clear that it had a long and interesting prehistory going back as far as Gauss. But until the advent of computing machines it was a solution looking for a problem.
- T. W. K RNER, Fourier Analysis (1988)
Life as we know it would be very different without the FFT.
- CHARLES F. VAN LOAN, Computational Frameworks for the Fast Fourier Transform (1992)
The matrix-vector product y = F nx, where
is the key computation in the numerical evaluation of Fourier transforms. If the product is formed in the obvious way then O( n 2) operations are required. The fast Fourier transform (FFT) is a way to compute y in just O( n log n) operations. This represents a dramatic reduction in complexity.
The FFT is best understood (at least by a numerical analyst!) by interpreting it as the application of a clever factorization of the discrete Fourier transform (DFT) matrix F n.
If n = 2 t then the DFT matrix F n may be factorized as
where P n is a permutation matrix and
| Proof | See Van Loan [1182, 1992, Thm. 1.3.3]. |
The theorem shows that we can write y = F nx as
which is formed as a sequence of matrix-vector products. It is the sparsity of the A k (two...
