# Can the FFT reduce its computation load for specific sparse data patterns?

I am working on a signal processing application, which involves an IFT. My background is CS and not signal processing maths.

Consider an N-FFT configured with 256 "bins" (N = 256) for processing a 100Hz bandwidth. The application is in the a-priori position of knowing at a given time where the input data can be sparse, in terms of only a subset of the total bandwidth being active.

Ex: at time T, there is a signal in a band B of [26,40]Hz, while at [0,25) and (40,100] Hz the signal is zero.

My questions are whether :

1. in such cases the 256-FFT could be configured to operate only as a 16-FFT (as B = 40 - 26 = 15, 2^2 < 15 <= 2^4) , and potentially avoid doing reams of computation as a 256-FFT where the add/multiply would be on zero values (and thus redundant) .

2. if so, professional impls of the FFT already do this (a quick scan of the input vector etc to determine whether such sparsity exists etc before beginning the computation proper) .

Can the FFT reduce its computation load for specific sparse data patterns?

Sort of but only of it's very sparse. You can always NOT use an FFT but implement the inverse FFT directly and omit the 0 terms from the sum.

We can guestimate the break even point. An FFT takes about 10 operations per butterfly and for a length 256 FFT you have 8 stages with 128 butterflies each, so you end up with about 10000 operations per FFT

For a direct inverse DFT you'll have for each real output sample about 3 operations per non-zero frequency coefficient. In this case the break even point comes out to be 13 or thereabouts.

Your case of 16 is probably close to a wash, so I wouldn't bother.

• Thanks for the info. The example was basic, in the hope that it would allow a simple explanation of the nuances of the FFT to be given to a layman. The application in reality will have N = 2048 / 4096, with the signal spread over a bandwidth of 10 - 2000 MHz, and input arriving at a rate of 1-20 microseconds. Hence the "thinking aloud" as to whether for the narrow(er) band occurrences (which are known a-priori for each input) could be better served by only using a fraction of the processing configuration that the full FFT will have. Feb 16 at 17:33

if so, professional impls of the FFT already do this (a quick scan of the input vector etc to determine whether such sparsity exists etc before beginning the computation proper) .

That can't be done – as far as I understood your question, the sparsity is in the other domain, and hence can't be seen in the input data without a transfrom. If saving effort on your main operation requires you to perform the most of your main operation, then it's usually not worth doing.

Even if it's the other way around, and your input is actually already mostly zeros, you'd need to be very smart at identifying, at runtime, which calculations not to do and skip them to be more effective than actually doing a few unnecessary 0-operand operations.

Generally, your FFT size suggests that doing less branching and more linear memory access helps performance more than trying to be smart about the FFT, assuming your CPU has anything like a cache, or branch prediction, or SIMD.

Unless you're on a really skimpy microcontroller, 100 transforms of size 256 per second are also pretty much negligible in computational effort, too, so if I was looking for something to computationally optimize, it would probably be something else.