Largest FFT to date

November 19, 2009 8:18 PM

What size was the largest (Fast) Fourier Transform ever performed to date? How many array elements? Can anyone beat 16,384³ complex-to-complex?
posted by mqk to Computers & Internet (8 answers total)

Because the FFT is broken into discreet bins, doing a transform of a long series is an O(n) operation. The length of a series that you can transform seems less interesting than your throughput, some example benchmarks here.
posted by idiopath at 8:55 PM on November 19, 2009

Response by poster: Last I checked FFT was O(N logN). Regardless, I'm interested in the largest FFT performed for any (scientific or not) application. Specifically I care about the case labeled "double-precision complex, 3d transforms, powers of 2" in your link. The largest array considered there was 128³; I'm asking if anyone has ever heard of an FFT being performed on an array larger than 16,384³. This would obviously have to been done in parallel, and memory constraints are probably more important than runtime.
posted by mqk at 9:25 PM on November 19, 2009

Do I understand correctly that you are talking about bin size here, and not length of the series? Either way I clearly misunderstood your question. With a given bin size FFT is O(N) for length of the series being analyzed, because there is no dependency between one bin and the next.
posted by idiopath at 9:32 PM on November 19, 2009

Response by poster: Bin size? Length of series? I think we're somehow misunderstanding each other... By Fourier Transform I mean this (specifically the "Multidimensional FFTs" section).
posted by mqk at 9:53 PM on November 19, 2009

OK, yeah, bin size and length of series are the kinds of terms that would come up in the field where I would use FFTs, audio synthesis and analysis. Because people want to use the data in real time the audio stream is broken up into partially overlapping bins, which are analyzed in parallel, since you cannot just wait for the entire stream, and wavelengths longer than 20hz tend to be uninteresting in audio usage.

I misunderstood how much of this was particular to my own domain, and apologize for the noise.
posted by idiopath at 10:00 PM on November 19, 2009

Keep in mind that the true answer is probably classified (NSA SigInt).
posted by ZenMasterThis at 6:20 AM on November 20, 2009

Hey mqk. ::waves::

I was thinking what ZenMasterThis said, that what you're asking about is for published FFTs, but no matter what, the NSA or Homeland Security or the bad guys or Blofeld or whoever has probably done one bigger, and you'll never know about it. Sorry!
posted by secretseasons at 8:41 AM on November 20, 2009

Yeah. A very good friend of mine used to work for a contractor to US gov't spook agencies, doing signal intelligence stuff. Whenever I asked questions about the cool toys he worked with and what kind of horsepower they had, he'd always say "Um, ... I can't tell you that."
posted by ZenMasterThis at 1:22 PM on November 20, 2009