As shown in the last subsection, kernel density estimates can be expressed as a submatrix of a certain convolution. The fast Fourier transform (FFT) is a computationally effective method for computing such convolutions. For a reference on this material, see Press et al. (1988).
The discrete Fourier transform of a complex vector is the vector , where

and i is the square root of –1. The vector can be recovered from by applying the inverse discrete Fourier transform formula

Discrete Fourier transforms and their inverses can be computed quickly using the FFT algorithm, especially when N is highly composite; that is, it can be decomposed into many factors, such as a power of 2. By the discrete convolution theorem, the convolution of two vectors is the inverse Fourier transform of the elementbyelement product of their Fourier transforms. This, however, requires certain periodicity assumptions, which explains why the vectors and require zeropadding. This is to avoid wraparound effects (see Press et al.; 1988, pp. 410–411). The vector is actually mirrorimaged so that the convolution of and will be the vector of binned estimates. Thus, if S denotes the inverse Fourier transform of the elementbyelement product of the Fourier transforms of and , then the first g elements of S are the estimates.
The bivariate Fourier transform of an complex matrix having entry equal to is the matrix with entry given by

and the formula of the inverse is

The same discrete convolution theorem applies, and zeropadding is needed for matrices and . In the case of , the matrix is mirrorimaged twice. Thus, if S denotes the inverse Fourier transform of the elementbyelement product of the Fourier transforms of and , then the upperleft corner of S contains the estimates.