[SciPy-User] [OT, FFT] FFT of signal larger than processor

[Moore, Eric (NIH/NIDDK) [F]]

> -----Original Message-----
> From: OlyDLG [mailto:d_l_goldsmith at yahoo.com]
> Sent: Monday, April 07, 2014 7:12 PM
> To: scipy-user at scipy.org
> Subject: [SciPy-User] [OT, FFT] FFT of signal larger than processor
> 
> Hi!  This Q came up at my work and I said I'd post here to see if
> anyone had
> any reference suggestions.  We need to FFT a series that uses up to 64K
> RAM
> to process, but we're downsizing the processing core to 8K RAM; we have
> 2
> kinds of supplementary flash memory available: "on-chip" (limited
> supply,
> faster read/writes) & "off-chip" (ample supply, slower read/writes).
> Are
> there known algorithms for FFT-ing a series piecemeal?  Such that
> minimize
> the number of data exchanges between storage and processor?
> References?
> Thanks!
> 
> OlyDLG
> 

You can do this by implementing one round of the FFT by hand and then doing all of the smaller transforms using the library call.  I can probably dig up some Matlab code which should be straightforward for you to translate if you're interested. 

When I was doing this, the problem was heavily IO bound as you've indicated. But all I had were spinning disks so perhaps it won't be quite as bad for you.  I could never find anything helpful about any algorithmic improvements when I looked, but I had trouble finding a search term that would bring me anything useful.

Eric