Fast Fourier Transforms Part 1: Cooley-Tukey | Hacker News Reader

Fast Fourier Transforms Part 1: Cooley-Tukey

connorboyle.io

95 pointssigna1133 comments

At the root of the fast transform is the simple fact that

    ax + bx = (a+b)x

The right hand side has fewer arithmetic operations. It's about finding common factors and pushing parentheses in. Because of the inherent symmetry of the FT expression there are lots of opportunities for this optimization.

Efficient decoding of LDPC codes also use the same idea. LDPCs were quite a revolution (pun intended) in coding/information theory.

On the other hand, something completely random, few days ago I found out that Tukey (then a Prof) and Feynman (then a student) along with other students were so enamored and intrigued by flexagons that they had set up an informal committee to understand them. Unfortunately their technical report never got published because the war intervened.

Strangely, it does not find a mention in Surely You're Joking.

How is belief propagation used for decoding LDPC codes related to FFT?

At the core both derive their optimization from the distributive property. If the expression graph has symmetry, you get more optimization out of it.

https://www.cs.ubc.ca/~murphyk/Teaching/Papers/GDL.pdf

Check out the first paragraph

    THE humble distributive
    law, in its simplest form
    states that...this leads
    to a large family of fast
    algorithms, including 
    Viterbi’s algorithm and 
    the fast Fourier
    transform (FFT).

Two extremely influential papers appeared back to back in transactions information theory. This is one of them.

The other is

https://vision.unipv.it/IA2/Factor graphs and the sum-product algorithm.pdf

Both are absolute gems of papers. The editor made sure that both appear in the same volume.

The second link is broken on HN because it contains a space. Here's a clickable version: https://vision.unipv.it/IA2/Factor%20graphs%20and%20the%20su...

Interesting, of course many computations can be expressed as a graph. In the case of the bipartite graph we perform belief propagation on to decode LDPC where is the optimization from the distributive property? The parity matrix would typically be constructed so that there's few subexpression to factor out, to maximize the error correcting properties.

I agree both FFT and belief propagation can be expressed as message passing algorithms.

It shows up in pushing in the parenthesis and pulling common terms out in the expression that is a sum (over all possible assignments) of products of terms.

Doing the summation the naive way will be exponential in the number of variables. The goal is to this in an efficient way exploiting the distributive property and symmetry if any, much like in the FFT case.

This can be done efficiently, for example, when the graph is a tree. (Even if it isn't, one can pretend as if it is. Surprisingly that often works very well but that's a different topic entirely)

Read the paper it's not difficult to follow.

There’s a whole subfield called generalized distributive law https://en.wikipedia.org/wiki/Generalized_distributive_law

> At the root of the fast transform is the simple fact that

Actually... no? That's a constant factor optimization; the second expression has 75% the operations of the first. The FFT is algorithmically faster. It's O(N·log2(N)) in the number of samples instead of O(N²).

That property doesn't come from factorization per se, but from the fact that the factorization can be applied recursively by creatively ordering the terms.

It's the symmetry that gives recursive opportunities to apply the optimization. It's the same optimization folded over and over again. Butterfly diagrams are great for understanding this. https://news.ycombinator.com/item?id=45291978 has pointers to more in depth exploration of the idea.

Well, actually ... Summation is linear time, multiplication is superlinear (eg n log n in number of digits).

Meaning that this takes k summations and one multiplication rather than k multiplications and k summations.

... Where k is the number of terms.

"Digits" are constant in an FFT (or rather ignored, really, precision is out of scope of the algorithm definition).

Obviously in practice these are implemented as (pairs of, for a complex FFT, though real-valued DCTs are much more common) machine words in practice, and modern multipliers and adders pipeline at one per cycle.

The part about complex numbers needs some intuition to build. This comes up in linear algebra in very relevant ways too, for example in 3D computer graphics calculations.

This is just my 2 cents, but I don’t have an intuition built for complex numbers.

I have recently needed a decently performing FFT. Instead of doing Cooley-Tukey, I have realized the bruteforce version essentially computes two vector×matrix products, so I have interleaved and reshaped the matrices for sequential full-vector loads, and did bruteforce version with AVX1 and FMA3 intrinsics. Good enough for my use case of moderately sized FFT where matrices fit in L2 cache.

I'm curious why you wouldn't just use a library like FFTW or Intel's IPP (or NVidia's cuFFT if applicable) ?

For FFTW the showstopper was GPL license. For IPP, 200 MB of binary dependencies, also I remember when Intel was caught testing for Intel CPUs specifically in their runtime libraries instead or CPUID feature bits, deliberately crippling performance on AMD CPUs. I literally don’t have any Intel CPUs left in this house. For cuFFT, the issue is vendor lock-in to nVidia.

And the problem is IMO too small to justify large dependencies. I only needed like 200×400 FFT as a minor component of a larger software.

It would be interesting to see how it compares to https://gitlab.mpcdf.mpg.de/mtr/pocketfft. The c++ branch is header only. I believe this is what scipy uses by default

Fast Fourier transform was not invented by Cooley-Tukey, it was used by Gauss to compute trigonometric interpolation of orbits from observations.

The factorization trick was reinvented several times. The algorithm that uses it to do a frequency decomposition was presented just once by named authors. This happens all the time. Freaking out about naming and attribution isn't really very informative.

Edit: as always, Wikipedia is a better source than comment pedantry: https://en.wikipedia.org/wiki/Fast_Fourier_transform#History

The wikipedia article you reference confirms my point:

"Gauss wanted to interpolate the orbits from sample observations; his method was very similar to the one that would be published in 1965 by James Cooley and John Tukey, who are generally credited for the invention of the modern generic FFT algorithm."

> Freaking out about naming and attribution isn't really very informative.

It matters who gets the credit for an original idea. Cooley and Tukey are lionized as pioneers, but they are not.

You’re pulling a quote that disproves your point.

There must be something wrong with your reading skills, because it's literally the same point slightly rephrased.

True. Before Fourier did Fourier.

This website appears broken in a very unique way on my iOS device. Whenever I swipe to scroll, the page gets zoomed out and it zooms back in when I stop swiping, but half of the content is cut off.

Same here. I think is intended as “feature” but extremely annoying.

I'm struggling to imagine what the feature is intended to be. Being able to see a larger portion of the page while scrolling? This...doesn't help at all, sadly.

Quite funny because now I can’t access the comment box at all.

> I find they often use the phrase “fast Fourier transform” (or perhaps more often, the abbreviation “FFT”) when they mean “discrete Fourier transform” (or “DFT”).

Preach it, brother.

Author here: thanks for sharing!

I agree with your opinion about the naming being confusing. Specifically regarding your mathematician friend what would you lose by taking a fast Fourier transform over a normal Fourier transform? Well the two aren't interchangeable. You would lose continuous time / frequency!

Some personal preference:

I find it hard to read the grey text on a white background that you have, and it's probably just a fundamental limit of reader mode in firefox, but it doesn't render mathml right. To read it I zoomed in, but then there were CSS issues where the content overlapped the sidebar.

While |x| is common to reference the length of a set I've not really seen that to reference the number of elements in a vector in the fields where I've used discrete Fourier transforms. I've always just defined N as the length of my vector. I honestly read it at first as the norm of x, and the norm of F{x} and thought you might be about to talk about Parseval's theorem.

Enjoyable enough and accurate article though. Thanks!

Thanks for reading and commenting.

I used "|x|" notation because I don't like introducing new unknown names if I don't have to. Too bad the annotation is ambiguous; I'll make a note about it.

If you right-click on the math blocks, you can change some of the parameters of the MathJAX renderer. One feature I've found helpful is the "click to zoom" which can be activated by following `Math Settings -> Zoom Trigger -> Click`.

I tried changing the text color. How does it look to you now?

I find the new text color easier to read. I hope everyone else shares my opinion since you put some work into catering to it.

Math notation is not great generally. There are canonical notations for somethings, and some times they're overloaded. Not much to do about it other than know about it.

Annoyingly you have to "know your audience" to get your math notation right for who you're presenting to. (You can never really do that on the Internet)

As an electrical engineer who's done a lot of DSP and worked with mathematicians I can point out some things that look either odd or normal depending on who I'm talking to. You can never really win with notation -- you'll always be wrong to someone =), but there are choices that are maybe less wrong for one discipline or another.

All that to say keep writing! You're doing pretty well!

This looks super interesting, but on my ancient iPhone, it zooms way out when I try to scroll, making it quite hard to read.

Author here: sorry, I've only recently discovered my blog is unusable for some iOS users. I'll try to fix it in the near future

Reply on news.ycombinator.com