begriffs

FFT With Circat

December 14, 2015
Newsletter ↳

David Banas uses the Fast Fourier Transform (FFT) in his daily work and is trying to find a way to make the calculation faster. His approach to this specific problem illustrates how to work at a high level of abstraction to minimize definition and maximize derivation.

Summary

  • David works with the Fast Fourier Transform which can be optimized with a logarithmic breakdown
  • Conal Elliott used a similar technique to find a solution to the “parallel scan” problem at below the order of algorithmic complexity previously believed to be a theoretical minimum
  • Can we implement FFT below \(O(n\log{}n)\)?
  • David wrote TreeViz to visualize ways of breaking the computations down. The visualizations would help in attacking the FFT problem
  • Example of a dataflow graph
  • To build a general purpose FFT, why not start with how it operates on simple structures, then derive the more complicated cases?
  • Conal’s Mantra: “Minimal definition, maximal derivation!”
  • Circat represents circuits (and other things) using cartesian closed categories
    • It compiles regular Haskell right down into Verilog
  • The reason Circat is applicable to David’s work is its data structures and operations
    • It allows us to express FFT at a much higher level of abstraction than we typically do
    • We’ll use RTree, a perfect binary leaf tree parameterized only by its depth
    • It’s nice for FFT because it enforces a \(\log_2\) breakdown of any input vector
  • Example of transition from list-based FFT (circa 2014) to the RTree way
  • Dive into the code
  • Future directions
    • Making FFT a typeclass
    • At first glance it’s not too significant, just a syntactic shuffle
    • But it may serve as a stepping stone toward defining primitives and deriving more complex structures
    • For instance they have defined a phasor for any Foldable
    • Next steps: define FFT instances for Id, Pair, and functor composition
    • Then use them to derive more complex structures on pairs of trees or trees of pairs
  • If you find this interesting David and Conal would love your help!