begriffs

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!