Fast Fourier Transforms (FFT) - General Introduction
The interpretation of the results of spectrum analysis is discussed in Basic Notation and Principles; however, we have not described how it is done computationally. Up until the mid-1960s, the standard way of performing the spectrum decomposition was to use explicit formulae to solve for the sine and cosine parameters. The computations involved required at least N2 (complex) multiplications. Thus, even with today's high-speed computers , it would be very time consuming to analyze even small time series (e.g., 8,000 observations would result in at least 64 million multiplications).
The time requirements changed drastically with the development of the so-called fast Fourier transform algorithm, or FFT for short. In the mid-1960s, J.W. Cooley and J.W. Tukey (1965) popularized this algorithm which, in retrospect, had in fact been discovered independently by various individuals. Various refinements and improvements of this algorithm can be found in Monro (1975) and Monro and Branch (1976). Readers interested in the computational details of this algorithm may refer to any of the texts cited in the Overview. Suffice it to say that via the FFT algorithm, the time to perform a spectral analysis is proportional to N*log2(N) -- a huge improvement.
However, a draw-back of the standard FFT algorithm is that the number of cases in the series must be equal to a power of 2 (i.e., 16, 64, 128, 256, ...). Usually, this necessitated padding of the series, which, as described above, will in most cases not change the characteristic peaks of the periodogram or the spectral density estimates. In cases, however, where the time units are meaningful, such padding may make the interpretation of results more cumbersome. As described below, the implementation of spectral analysis in the Time Series module does not impose any restrictions on the length of the input series.