Haskell FFT posts

  1. The Discrete Fourier Transform Introduction to the DFT and a naïve implementation.

  2. Matrix factorisation The Cooley-Tukey approach to factorising Fourier matrices.

  3. Cooley-Tukey for Powers of Two The “textbook” Cooley-Tukey algorithm for powers-of-two input lengths.

  4. A Simple Application Audio filtering example.

  5. Transforming Vectors of Arbitrary Lengths Extending the Cooley-Tukey idea to arbitrary input lengths.

  6. Implementing the Mixed-Radix FFT Haskell code (and testing) for the arbitrary length Cooley-Tukey algorithm.

  7. Where We’ve Got To, Where We’re Going Taking stock.

  8. Benchmarking Experiments Benchmarking with Criterion, and a plan for optimisation.

  9. Prime-Length FFT With Rader’s Algorithm Dealing with prime input lengths— some number theory, some group theory, and achieving $O(N \log N)$ scaling.

  10. Building a package Code organisation.

  11. Optimisation Part 1 Mutable vectors, unboxing.

  12. Optimisation Part 2 Plan generation: heuristics and empirical plan selection.

  13. Optimisation Part 3 Improvements to Rader’s algorithm, compiler flags, final benchmarking.

  14. Wrap-up What we’ve done, lessons learned, what’s left to do.