How is belief propagation used for decoding LDPC codes related to FFT?
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).
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.
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.