FFT versus Direct Convolution

International Standard Book Number — Click for https://mathworld.wolfram.com/ISBN.html

In digital signal processing, FIR is an acronym for Finite Impulse Response — Click for https://ccrma.stanford.edu/~jos/filters/FIR_Digital_Filters.html

A filter in the audio signal processing context is any operation that accepts a signal as an input and produces a signal as an output. Most practical audio filters are linear and time invariant, in which case they can be characterized by their impulse response or their frequency response. — Click for https://ccrma.stanford.edu/~jos/filters/What_Filter.html

An Finite Impulse Response (FIR) digital filter has an impulse response that reaches zero in a finite number of samples. Such filters cannot have any feedback loops. FIR filters are also called nonrecursive. The transfer function of an FIR filter is a polynomial. — Click for https://ccrma.stanford.edu/~jos/filters/FIR_Digital_Filters.html

The compiler transforms human-readable source code into machine-readable code. — Click for http://en.wikipedia.org/wiki/Compiler

Matlab is a high-level scripting language for scientific computing — Click for https://ccrma.stanford.edu/~jos/matlab/

Click for https://ccrma.stanford.edu/~jos/mdft/Convolution.html

Fast Fourier Transforms (FFT) are fast algorithms for computing the Discrete Fourier Transform (DFT) — Click for https://ccrma.stanford.edu/~jos/mdft/Fast_Fourier_Transform_FFT.html

FFT versus Direct Convolution

Using the Matlab test program in [264],^9.1FFT convolution was found to be faster than direct convolution starting at length (looking only at powers of 2 for the length ).^9.2 FFT convolution was also never significantly slower at shorter lengths for which ``calling overhead'' dominates.

Running the same test program in 2011,^9.3 FFT convolution using the fft function was found to be faster than conv for all (power-of-2) lengths. The speed of FFT convolution divided by that of direct convolution started out at 14 for , fell to a minimum of at , above which it started to climb as expected, reaching at $N=2^{16}=65,536$ . Note that this comparison is unfair because the Octave fft function is a dynamically linked, separately compiled module, while conv is written in the matlab language and thus suffers more overhead from the matlab interpreter.

An analysis reported in Strum and Kirk [279, p. 521], based on the number of real multiplies, predicts that the fft is faster starting at length , and that direct convolution is significantly faster for very short convolutions (e.g., 16 operations for a direct length-4 convolution, versus 176 for the fft function).

In digital audio, FIR filters are often hundreds of taps long. For such filters, the FFT method is much faster than direct convolution in the time domain on single CPUs. On GPUs, FFT convolution is faster than direct convolution only for much longer FIR-filter lengths (in the thousands of taps [242]); this is because massively parallel hardware can perform an ${\cal O}(N^2)$ algorithm (direct convolution) faster than a single CPU can perform an ${\cal O}(N\,\lg N)$ algorithm (FFT convolution).

FFT versus Direct Convolution

``Spectral Audio Signal Processing'', by Julius O. Smith III, W3K Publishing, 2011, ISBN 978-0-9745607-3-1. Copyright © 2022-02-28 by Julius O. Smith III Center for Computer Research in Music and Acoustics (CCRMA), Stanford University

``Spectral Audio Signal Processing'', by Julius O. Smith III, W3K Publishing, 2011, ISBN 978-0-9745607-3-1.
Copyright © 2022-02-28 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA), Stanford University