DiscreteTransforms[FourierTransform]  compute the discrete Fourier transform
DiscreteTransforms[InverseFourierTransform]  compute the discrete inverse Fourier transform

Calling Sequence


FourierTransform(Z, [,options])
FourierTransform(Z1, nelem [,options])
FourierTransform(Zn, dim [,options])
FourierTransform(X, Y [,options])
FourierTransform(X1, Y1, nelem [,options])
FourierTransform(Xn, Yn, dim [,options])
InverseFourierTransform(Z, [,options])
InverseFourierTransform(Z1, nelem [,options])
InverseFourierTransform(Zn, dim [,options])
InverseFourierTransform(X, Y [,options])
InverseFourierTransform(X1, Y1, nelem [,options])
InverseFourierTransform(Xn, Yn, dim [,options])


Parameters


Z



complex data Array, 15 dimensional

Z1



complex data Array, 1 dimensional

Zn



complex data Array, 25 dimensional

X, Y



real data Arrays, 15 dimensional

X1, Y1



real data Arrays, 1 dimensional

Xn, Yn



real data Arrays, 25 dimensional

nelem



number of discrete data points to use in the transform

dim



Array dimension to be transformed

options



optional argument of the type option=value, where option is one of algorithm, padding, inplace, workingstorage, and normalization





Description


•

The FourierTransform and InverseFourierTransform commands compute the forward and inverse
Fourier transform
of the numerical input data. For the single data Array form, the input data Z is interpreted as a complex Array. For the two data Array form, the inputs X,Y are interpreted as the real and imaginary parts of the data, respectively.


Note: The FourierTransform and InverseFourierTransform commands work strictly in hardware precision, so their accuracy is independent of the setting of Digits. Additionally, in all cases, the input data must either be floatingpoint numerical data, or must evaluate to floatingpoint numerical data. Symbolic entries are not allowed.

•

The definition in use for a 1D point forward transform of the data is given by


And the definition for the inverse transform by


where symmetric normalization by is in use (this can be changed via the normalization option).

•

If the input data is a onedimensional Array, then the number of elements in the Array to be used for the transform can be specified as nelem. This allows reuse of the same storage for different sized transforms (and also inplace output with padding  see inplace and padding below).

•

If the input data is an Array of dimension greater than 1, or a Matrix, then by default a transform is performed with respect to all dimensions of the input for all combinations of the indices. In this case, the data lengths cannot be specified.


For example, calling FourierTransform or InverseFourierTransform with a complex 20x30 Matrix performs a 20 data point transform for each of the 30 columns of the Matrix data, followed by a 30 data point transform for each of the 20 rows of the (already once transformed) Matrix data.


Specification of dim tells FourierTransform or InverseFourierTransform to perform a transform only along that Array dimension, or for the 20x30 Matrix example, specification of dim=1 transforms with respect to the Matrix rows, performing a 20 data point transform for each column of the Matrix, while specification of dim=2 transforms with respect to the Matrix columns, performing a 30 data point transform for each row of the Matrix.



Options



Optional arguments control the way in which the Fourier or inverse Fourier transform is performed.


Where alg can be set to mintime (default), minstorage, or DFT. The mintime algorithm is an efficient implementation of the twiddle factor FFT algorithm from Brigham. The minstorage algorithm is a variant of the same algorithm that has been modified to use as little additional storage as possible. For more information, see FourierTransform/efficiency. The DFT algorithm is simply the discrete Fourier transform (very slow, and provided primarily for educational purposes).


Here num specifies the maximum amount of zero padding that can be used to more efficiently compute the Fourier transform. The mintime and minstorage algorithms are fast Fourier transform algorithms, and as such, are more efficient when the data length is a highly composite number (that is, has many small integer factors). By default, no zero padding is used, so for computations where the data length is actually a large prime, the mintime and minstorage algorithms are as inefficient as the DFT algorithm. It is generally advisable to collect the transform data with a highly composite number of data points, so no padding is needed, and the transform can be computed efficiently. For more information, see FourierTransform/efficiency.


Note: It is not generally possible to use padding and inplace output, as the output data length can exceed the size of the input data, so there is insufficient space in the input to store the result. The only exception is when a 1D transform is being performed, and the specified data length nelem plus the maximal padding will fit in the input Array. In this case the output can be provided inplace.


Here data must be a complex valued rectangular Vector or Matrix with between m*n and 2*m*n entries (where m is the number of transforms being computed, and n is the data length of the transform). This storage is then used as working storage, preventing the algorithm from allocating any additional storage. Note that this is not required for the DFT algorithm. The quantity of additional storage required depends upon the data length. If the data length is prime, then the required storage is 2*m*n, but for all other cases, the required storage is m*n.

•

normalization=symmetric (default), none or full

•

The output from FourierTransform and InverseFourierTransform is in two forms, which are different only if padding is in use or not.


Without padding, the output is simply the single Array (for the single complex input form) or a two element sequence containing the pair of Arrays (for the separated real/imaginary part form) that contain the computed transform of the input data. For inplace operation, these output Array(s) are the same as the input Array(s).


If padding is in use, a list representing the data lengths used for the transform is the first element of the output sequence, followed by the data (1 or 2 Arrays).


Efficiency



The most efficient transform can be obtained when the data length(s) are highly composite, the input data has , and the computation is being performed inplace. Input data with any other datatype is copied to a data Array for the computation, then transformed back to the input datatype on output. For more information, see FourierTransform/efficiency.




Examples


>


>


Transform of 1D complex Vector.
>


 (1) 
>


 (2) 
>


>


 (3) 
Transform of 2 1D real Vectors (real and imaginary parts).
>


 (4) 
>


 (5) 
>


 (6) 
>


 (7) 
1D transform with padding.
>


 (8) 
>


 (9) 
A data length of 64, which has 2 as the largest prime factor, was used.
If the input Array is made larger, but the data length is still specified as 60, then inplace output is also possible:
>


 (10) 
>


 (11) 
Twodimensional transform, one dimension at a time, and both at once:
>


 (12) 
Transform with respect to rows then columns.
>


 (13) 
>


 (14) 
Transform both at once (inplace):
>


 (15) 
>


 (16) 


References



Brigham, E.O. The Fast Fourier Transform. New Jersey: PrenticeHall Inc., 1974.


