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.
HarHarVeryFunny 28 minutes ago [-]
I'm curious why you wouldn't just use a library like FFTW or Intel's IPP (or NVidia's cuFFT if applicable) ?
srean 6 hours ago [-]
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.
rigtorp 4 hours ago [-]
How is belief propagation used for decoding LDPC codes related to FFT?
srean 2 hours ago [-]
At the core both derive their optimization from the distributive property. If the expression graph has symmetry, you get more optimization out of it.
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.
Both are absolute gems of papers. The editor made sure that both appear in the same volume.
rigtorp 5 minutes ago [-]
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.
> 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.
srean 2 hours ago [-]
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.
emil-lp 2 hours ago [-]
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.
ajross 2 hours ago [-]
"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.
terabytest 8 hours ago [-]
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.
bonefolder 7 hours ago [-]
Quite funny because now I can’t access the comment box at all.
f1shy 8 hours ago [-]
Same here. I think is intended as “feature” but extremely annoying.
sunrunner 6 hours ago [-]
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.
6 hours ago [-]
Mikhail_K 5 hours ago [-]
Fast Fourier transform was not invented by Cooley-Tukey,
it was used by Gauss to compute trigonometric interpolation of orbits from observations.
ajross 4 hours ago [-]
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.
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.
https://www.cs.ubc.ca/~murphyk/Teaching/Papers/GDL.pdf
Check out the first paragraph
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.
I agree both FFT and belief propagation can be expressed as message passing algorithms.
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.
Meaning that this takes k summations and one multiplication rather than k multiplications and k summations.
... Where k is the number of terms.
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.
Edit: as always, Wikipedia is a better source than comment pedantry: https://en.wikipedia.org/wiki/Fast_Fourier_transform#History