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 floating-point numerical data, or must evaluate to floating-point numerical data. Symbolic entries are not allowed.

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

And the definition for the inverse transform by

where symmetric normalization by $\sqrt{\frac{1}{N}}$ is in use (this can be changed via the normalization option).

If the input data is a one-dimensional Array, then the number of elements in the Array to be used for the transform can be specified as nelem. This allows re-use 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.

For more information on Fourier transforms in Maple, including a summarized comparison of DiscreteTransforms[FourierTransform], SignalProcessing[FFT], and SignalProcessing[DFT], see Fourier Transforms in Maple.

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

algorithm=alg

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 $\mathrm{O}\left(N^2\right)$ discrete Fourier transform (very slow, and provided primarily for educational purposes).

padding=num

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.

inplace=bool

Here bool can have the value true or false and specifies whether the output overwrites the input. By default this is false. Further, if a single input Array is used, with a float data type (that is, $\mathrm{float}$, ${\mathrm{float}}_8$ or $\mathrm{sfloat}$) then inplace output cannot be used, as the complex result cannot be stored in the input.

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 1-D 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.

workingstorage=data

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 process of performing a forward transform followed by an inverse transform, without normalization, introduces a factor of n to the data values. Three normalizations are in common use, including symmetric normalization (the default), where the data is multiplied by $\frac{1}{\sqrt{n}}$ in both transform directions. The other two cases correspond to performing no normalization on the forward transform, and $\frac{1}{n}$ normalization on the inverse transform, and the reverse of this. Specification of normalization=none on a transform will prevent normalization, while specification of normalization=full will perform $\frac{1}{n}$ normalization, so by consistent use of this this option between the forward and inverse transformations, one can obtain any of the three normalizations commonly used in practice.

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).

$\mathrm{with}\left(\mathrm{DiscreteTransforms}\right)\:$

$\mathrm{Digits}≔15\:$

$Z≔\mathrm{Vector}\left(5\,i\mapsto \mathrm{evalf}\left(\exp \left(\frac{\mathrm{I}}{3}\cdot i\right)\right)\,\mathrm{datatype}=\mathrm{complex}\left[8\right]\right)$

$Z≔\left[\begin{array}{c}0.944956946314738+0.327194696796152\mathrm{I}\\ 0.785887260776948+0.618369803069737\mathrm{I}\\ 0.540302305868140+0.841470984807897\mathrm{I}\\ 0.235237573302993+0.971937901363312\mathrm{I}\\ \mathrm{-0.0957235480143790}+0.995407957751765\mathrm{I}\end{array}\right]$

$\mathrm{Z2}≔\mathrm{FourierTransform}\left(Z\right)$

$\mathrm{Z2}≔\left[\begin{array}{c}1.07808016683995+1.67901037963378\mathrm{I}\\ 0.0427237445328346-0.741915464402484\mathrm{I}\\ 0.236451541664114-0.288930752395548\mathrm{I}\\ 0.323690442005380-0.0849440827896753\mathrm{I}\\ 0.432042072728096+0.168409503867555\mathrm{I}\end{array}\right]$

$\mathrm{InverseFourierTransform}\left(\mathrm{Z2}\,\mathrm{inplace}=\mathrm{true}\right)\:$

$Z-\mathrm{Z2}$

$\left[\begin{array}{c}0.-1.66533453693773\times {10}^{\mathrm{-16}}\mathrm{I}\\ 1.11022302462516\times {10}^{\mathrm{-16}}+1.11022302462516\times {10}^{\mathrm{-16}}\mathrm{I}\\ 0.-1.11022302462516\times {10}^{\mathrm{-16}}\mathrm{I}\\ 2.77555756156289\times {10}^{\mathrm{-17}}+0.\mathrm{I}\\ 8.32667268468867\times {10}^{\mathrm{-17}}+1.11022302462516\times {10}^{\mathrm{-16}}\mathrm{I}\end{array}\right]$

$X,Y≔\mathrm{Vector}\left(5\,i\mapsto \mathrm{evalf}\left(\cos \left(\frac{i}{3}\right)\right)\,\mathrm{datatype}=\mathrm{float}\left[8\right]\right),\mathrm{Vector}\left(5\,i\mapsto \mathrm{evalf}\left(\sin \left(\frac{i}{3}\right)\right)\,\mathrm{datatype}=\mathrm{float}\left[8\right]\right)$

$X,Y≔\left[\begin{array}{c}0.944956946314738\\ 0.785887260776948\\ 0.540302305868140\\ 0.235237573302993\\ \mathrm{-0.0957235480143790}\end{array}\right],\left[\begin{array}{c}0.327194696796152\\ 0.618369803069737\\ 0.841470984807897\\ 0.971937901363312\\ 0.995407957751765\end{array}\right]$

$\mathrm{X2},\mathrm{Y2}≔\mathrm{FourierTransform}\left(X\,Y\right)$

$\mathrm{X2},\mathrm{Y2}≔\left[\begin{array}{c}1.07808016683995\\ 0.0427237445328346\\ 0.236451541664114\\ 0.323690442005380\\ 0.432042072728096\end{array}\right],\left[\begin{array}{c}1.67901037963378\\ \mathrm{-0.741915464402484}\\ \mathrm{-0.288930752395548}\\ \mathrm{-0.0849440827896753}\\ 0.168409503867555\end{array}\right]$

$\mathrm{InverseFourierTransform}\left(\mathrm{X2}\,\mathrm{Y2}\,\mathrm{inplace}=\mathrm{true}\right)$

$\left[\begin{array}{c}0.944956946314738\\ 0.785887260776948\\ 0.540302305868140\\ 0.235237573302993\\ \mathrm{-0.0957235480143791}\end{array}\right],\left[\begin{array}{c}0.327194696796152\\ 0.618369803069737\\ 0.841470984807897\\ 0.971937901363312\\ 0.995407957751765\end{array}\right]$

$X-\mathrm{X2},Y-\mathrm{Y2}$

$\left[\begin{array}{c}0.\\ 1.11022302462516\times {10}^{\mathrm{-16}}\\ 0.\\ 2.77555756156289\times {10}^{\mathrm{-17}}\\ 8.32667268468867\times {10}^{\mathrm{-17}}\end{array}\right],\left[\begin{array}{c}\mathrm{-1.66533453693773}\times {10}^{\mathrm{-16}}\\ 1.11022302462516\times {10}^{\mathrm{-16}}\\ \mathrm{-1.11022302462516}\times {10}^{\mathrm{-16}}\\ 0.\\ 1.11022302462516\times {10}^{\mathrm{-16}}\end{array}\right]$

$Z≔\mathrm{Vector}\left(60\,i\mapsto \mathrm{evalf}\left(\exp \left(\frac{\mathrm{I}}{30}\cdot i\right)\right)\right)$

$\mathrm{Z2}≔\mathrm{FourierTransform}\left(Z\,\mathrm{padding}=10\right)$

$Z≔\mathrm{Vector}\left(70\&comma;i\mapsto \mathrm{`if`}\left(60<i\&comma;0\&comma;\mathrm{evalf}\left(\exp \left(\frac{\mathrm{I}}{30}\cdot i\right)\right)\right)\right)$

$\mathrm{Z2}≔\mathrm{FourierTransform}\left(Z\&comma;60\&comma;\mathrm{padding}=10\&comma;\mathrm{inplace}=\mathrm{true}\right)$

$Z≔\mathrm{Matrix}\left(3\&comma;4\&comma;\left(i\&comma;j\right)\mapsto {\left(i+j\right)}^2-\mathrm{I}\cdot i\&comma;\mathrm{datatype}=\mathrm{complex}\left[8\right]\right)$

$Z≔\left[\begin{array}{cccc}4.-\mathrm{I}& 9.-\mathrm{I}& 16.-\mathrm{I}& 25.-\mathrm{I}\\ 9.-2.\mathrm{I}& 16.-2.\mathrm{I}& 25.-2.\mathrm{I}& 36.-2.\mathrm{I}\\ 16.-3.\mathrm{I}& 25.-3.\mathrm{I}& 36.-3.\mathrm{I}& 49.-3.\mathrm{I}\end{array}\right]$

$\mathrm{Z2}≔\mathrm{FourierTransform}\left(Z\&comma;1\right)$

$\mathrm{Z2}≔\left[\begin{array}{cccc}16.7431578064991-3.46410161513775\mathrm{I}& 28.8675134594813-3.46410161513775\mathrm{I}& 44.4559707276012-3.46410161513775\mathrm{I}& 63.5085296108588-3.46410161513775\mathrm{I}\\ \mathrm{-4.40747728811182}+4.36602540378444\mathrm{I}& \mathrm{-6.13952809568070}+5.36602540378444\mathrm{I}& \mathrm{-7.87157890324957}+6.36602540378444\mathrm{I}& \mathrm{-9.60362971081845}+7.36602540378444\mathrm{I}\\ \mathrm{-5.40747728811182}-2.63397459621556\mathrm{I}& \mathrm{-7.13952809568070}-3.63397459621556\mathrm{I}& \mathrm{-8.87157890324957}-4.63397459621556\mathrm{I}& \mathrm{-10.6036297108184}-5.63397459621556\mathrm{I}\end{array}\right]$

$\mathrm{FourierTransform}\left(\mathrm{Z2}\&comma;2\&comma;\mathrm{inplace}=\mathrm{true}\right)$

$\left[\begin{array}{cccc}76.7875858022202-6.92820323027551\mathrm{I}& \mathrm{-13.8564064605510}+17.3205080756888\mathrm{I}& \mathrm{-15.5884572681199}+0.\mathrm{I}& \mathrm{-13.8564064605510}-17.3205080756888\mathrm{I}\\ \mathrm{-14.0111069989303}+11.7320508075689\mathrm{I}& 0.732050807568877-2.73205080756888\mathrm{I}& 1.73205080756888-0.999999999999999\mathrm{I}& 2.73205080756888+0.732050807568878\mathrm{I}\\ \mathrm{-16.0111069989303}-8.26794919243112\mathrm{I}& 2.73205080756888-0.732050807568877\mathrm{I}& 1.73205080756888+\mathrm{I}& 0.732050807568878+2.73205080756888\mathrm{I}\end{array}\right]$

$\mathrm{FourierTransform}\left(Z\&comma;\mathrm{inplace}=\mathrm{true}\right)$

$\left[\begin{array}{cccc}76.7875858022202-6.92820323027551\mathrm{I}& \mathrm{-13.8564064605510}+17.3205080756888\mathrm{I}& \mathrm{-15.5884572681199}+0.\mathrm{I}& \mathrm{-13.8564064605510}-17.3205080756888\mathrm{I}\\ \mathrm{-14.0111069989303}+11.7320508075689\mathrm{I}& 0.732050807568877-2.73205080756888\mathrm{I}& 1.73205080756888-\mathrm{I}& 2.73205080756888+0.732050807568877\mathrm{I}\\ \mathrm{-16.0111069989303}-8.26794919243112\mathrm{I}& 2.73205080756888-0.732050807568877\mathrm{I}& 1.73205080756888+\mathrm{I}& 0.732050807568877+2.73205080756888\mathrm{I}\end{array}\right]$

$Z-\mathrm{Z2}$

$\left[\begin{array}{cccc}0.+0.\mathrm{I}& 1.77635683940025\times {10}^{\mathrm{-15}}+0.\mathrm{I}& 1.77635683940025\times {10}^{\mathrm{-15}}+0.\mathrm{I}& 1.77635683940025\times {10}^{\mathrm{-15}}+0.\mathrm{I}\\ 1.77635683940025\times {10}^{\mathrm{-15}}+0.\mathrm{I}& 1.11022302462516\times {10}^{\mathrm{-16}}+8.88178419700125\times {10}^{\mathrm{-16}}\mathrm{I}& \mathrm{-4.44089209850063}\times {10}^{\mathrm{-16}}-7.77156117237610\times {10}^{\mathrm{-16}}\mathrm{I}& 4.44089209850063\times {10}^{\mathrm{-16}}-3.33066907387547\times {10}^{\mathrm{-16}}\mathrm{I}\\ 0.+0.\mathrm{I}& \mathrm{-8.88178419700125}\times {10}^{\mathrm{-16}}-7.77156117237610\times {10}^{\mathrm{-16}}\mathrm{I}& 1.33226762955019\times {10}^{\mathrm{-15}}-1.11022302462516\times {10}^{\mathrm{-16}}\mathrm{I}& \mathrm{-3.33066907387547}\times {10}^{\mathrm{-16}}+8.88178419700125\times {10}^{\mathrm{-16}}\mathrm{I}\end{array}\right]$

Brigham, E.O. The Fast Fourier Transform. New Jersey: Prentice-Hall Inc., 1974.