FFT
new to Analytica 4.5
FFT( x, T, Freq )
The Fast Fourier Transform (FFT) converts a time series of equally spaced values, «x», from the discrete time (or spatial) domain to the discrete frequency domain. «T» is the time index and «Freq» is the Frequency index, and these two indexes should have the same length. The time series, «x», is indexed by «T» and may be real or complex, and the result is indexed by «Freq» and contains complex numbers in general. The units of «Freq» are cycles per «units of T».
The FFTInv function does the inverse transformation from the frequency domain back to the time (or spatial) domain.
The Discrete Fourier Transform
The FFT computes the discrete Fourier transform (DFT) in an efficient manner. The DFT is defined given by
- [math]\displaystyle{ H_k = \sum_{i=0}^{n-1} x_i e^{2j\pi i k/n} }[/math]
where [math]\displaystyle{ j }[/math] is the imaginary number [math]\displaystyle{ \sqrt{-1} }[/math], and n is the number of points in «T» and «Freq». This is a discrete approximation to the continuous Fourier Transform given by
- [math]\displaystyle{ H(f) = \int_{-\infty}^\infty x(t) e^{2j \pi f t} dt }[/math]
Units and spacing
Let [math]\displaystyle{ \Delta t }[/math] denote the spacing between points in «T» and [math]\displaystyle{ n }[/math] be the number of points. Then the spacing [math]\displaystyle{ \Delta F }[/math] of the points in «Freq» is [math]\displaystyle{ 1/n\Delta t }[/math]. The quantity [math]\displaystyle{ 1/\Delta t }[/math] is called the sampling frequency, which should be at least twice the smallest frequency that is present in the underlying continuous signal.
For example, suppose your time series is sampled at 1000Hz for just over 10 seconds, so that [math]\displaystyle{ \Delta t=1 millisecond }[/math] and [math]\displaystyle{ n=10K }[/math]. Then [math]\displaystyle{ \Delta F=0.1 Hz }[/math]. It would make sense to define «Freq» as (0..10K-1)*0.1 so that the numeric values of «Freq» are in Hertz.
Efficiency
The FFT is a fast implementation of the Discrete Fourier Transform (DFT), which is most efficient when the number of elements in «T» and «Freq» is an even power of 2. Analytica's implementation is still considerably more efficient than a straight DFT as long as the number of elements in «T» is the product of several small factors. So, for example, it would still be very efficient when «T» has 531,441 items, since [math]\displaystyle{ 531441=3^{12} }[/math]. It is also pretty good on even powers of 10, since even powers of 10 have factors of 2 and 5, both of which are small numbers. The worst efficiency would occur when «T» has a prime number of elements, in which case the FFT would be equivalent in efficiency to a DFT and would have [math]\displaystyle{ O(n^2) }[/math] time complexity.
A straight DFT requires [math]\displaystyle{ O(n^2) }[/math] steps. If you were to apply this to a time series having n=1M points, it would require 1 trillion steps to compute, which is likely to be infeasible. The complexity of an FFT when the number of points is an even power of 2 is computed in [math]\displaystyle{ O(n \log(n)) }[/math] steps. For n=1M this comes out to 6 million steps, about 150,000 times faster than a straight DFT.
I haven't worked out the complexity for the case when n is not a power of 2, but is a product of small factors, but I think it should be something like [math]\displaystyle{ O(k n \log(n)) }[/math], where k is the largest factor and k « n.
Complications
Nyquist frequency, aliasing...
Enable comment auto-refresher