Fast Fourier Transform
DESCRIPTION:
Performs the fast Fourier transform on a vector or an array of either numeric or complex values.
USAGE: 
fft(z, inverse=F)
REQUIRED ARGUMENTS:
z:
numeric or complex vector or array.
OPTIONAL ARGUMENTS:
inverse:
logical flag: if TRUE, the inverse of the transform is computed.
VALUE:
the unnormalized discrete Fourier transform of the input data z (or the inverse transform if inverse=TRUE). This is of mode "complex".
DETAILS:
The fast Fourier transform algorithm is used. No padding of the input data is done; length(z) is factored, if possible, and the factorization is used in the algorithm. Therefore, if length(z) is prime, there will be no advantage in using fft over computing the transform explicitly.

If z is an array, fft will return the multi-dimensional unnormalized discrete Fourier transform of z-a complex array with the same shape as z. Therefore, using fft on a multivariate time series will not compute the time transform.

REFERENCES:
Bloomfield, P. (1976). Fourier Analysis of Time Series: An Introduction. Wiley, New York.

The chapter "Analyzing Time Series" in the S-PLUS Guide to Statistical and Mathematical Analysis.

SEE ALSO:
spectrum .