Algorithms for computing FFT in parallel I am trying to parallelize the computation of an FFT on terabyte-sized signal files. Right now such an FFT using an open-source library takes many hours, even running through CUDA on the fastest GPU I have. The framework I am trying to adapt to this process is Hadoop. In very basic terms, Hadoop distributes a problem over any number of server nodes in the following manner:


  • You split your input file into (key, value) pairs.
  •   These pairs
  are fed into a “Map” algorithm, which transforms your (key, value)
  pairs into some other (key, value) pairs based on what you put inside
  the Map.
  •   The framework then collects all the (key, value)
  outputs from the Maps and sorts them by key, as well as aggregating
  values with the same key to a single pair,  so you end up with (key, 
  list(value1, value2, ..)) pairs
   •  These  pairs are then
  fed into a “Reduce” algorithm, which in turn outputs more (key, value)
  pairs as your final result (written to a file).


There are many applications for this model in practical stuff like processing server logs, but I am having a hard time applying the framework to chopping up an FFT into “map” and “reduce” tasks, especially since I am not really familiar with DSP.

I will not bother you with the programming mumbo jumbo, as this is a DSP Q&amp;A. I am, however,  confused on what algorithms exist for computing FFTs in parallel; Map and Reduce tasks can’t (technically) talk to each other, so the FFT must be split into independent problems from which the results can somehow be recombined at the end.

I have programmed a simple implementation of Cooley-Tukey Radix 2 DIT that works on small examples, but using it for recursively calculating odd/even index DFTs for a billion bytes will not work.  I have spent a few weeks on reading many papers, including one on a MapReduce FFT algorithm (written by Tsz-Wo Sze as part of his paper on SSA multiplication, I cannot link more than 2 hyperlinks) and the “four-step FFT” (here and here), which seem similar to each other and to what I am trying to accomplish. However, I am hopelessly bad at mathematics, and applying any of those methods by hand to a simple set of something like {1,2, 3, 4, 5, 6, 7, 8} (with all imaginary components being 0) gives me wildly incorrect results. Can anyone explain an efficient parallel FFT algorithm to me in plain English (one that  I linked or any other) so that I may try and program it?

Edit: Jim Clay and anyone else who may be confused by my explanation, I am trying to do a single FFT of the terabyte file. But I want to able to do it concurrently on multiple servers in order to speed up the process.
I think your main problem isn't how to parallel the algorithm (which actually can be done) but it's numeric precision. 
FFTs of a size that large are numerically quite tricky. The FFT coefficients are of the form
$e^{-j\cdot 2\cdot \pi \cdot \frac{k }{N}}$ and if N is very large the coefficient calculation gets noisy. Lets say you have $N = 2^{40}$ and you use 64 bit double precision arithmetic. The first 1000 coefficients have a real part that's exactly unity (although it shouldn't be that way) so you will need higher precision math, which is very inefficient and cumbersome to use. 

You will also amass lots of rounding and truncation errors as the sheer number of operations that go into a single output number is very large too. Due to the "every output depends on every input" nature of the FFT, error propagation is rampant.

I'm not aware of an easy way to work around that. Your request is an unusual one. Most applications that do spectral analysis of large data sets do a running analysis where you don't have that problem. Perhaps if you can describe your application and it's constraints a but more, we can point you to a more suitable solution.