Fast Fourier Transform
This functionality does not run in MATLAB.
ReturnType = t>, <
ReturnType = t>, <
ReturnType = t>, <
numeric::fft(data) returns the discrete Fourier
The one-dimensional discrete Fourier transform F = fft(L) of N data elements Lj stored in the list L = [L1, …, LN] is the list F = [F1, …, FN] given by
fft transforms the data by a Fast Fourier
Transform (FFT) algorithm.
The d-dimensional discrete Fourier transform F = fft(A) of N = n1×···×nd data elements (Aj1, …, jd) stored in the array A is the array F = (Fk1, …, kd) given by
with k1 = 1, …, n1, …, kd = 1, …, nd.
Data provided by a list, or one-dimensional
hfarray are transformed according to
the one-dimensional transform. Data provided by matrices are transformed
according to the twp-dimensional transform. Data provided by multidimensional
arrays or hfarrays are transformed according to the multi-dimensional
transform matching the format of the input array.
If the data size N factorizes as N = p q,
the discrete Fourier transform can be computed by p different
Fourier transforms of subsets of the data, each subset having the
data size q.
The corresponding 'divide and conquer' algorithm is known as FFT ('Fast
Fourier Transform'). The
fft routine employs the
FFT algorithm. It is most efficient, when the data size N is
an integer power of 2 ('radix
2 FFT'). In this case, the algorithm needs
Note: More generally, FFT is efficient, if the data size is the product of many small factors.
Following Bluestein, the Fourier transform is written as a convolution if the data size N is a prime. The data are zero-padded to a data length that is an integer power of 2. The convolution is then computed via radix 2 FFTs. Thus, the algorithm needs elementary operations even if N is a prime.
Without the option
Symbolic, the function
is sensitive to the environment variable
DIGITS, which determines
the numerical working precision.
Compute one-dimensional transformations using lists. By default, numerical expressions are converted to floating-point values:
L := [1, 2^(1/2), 3*I, PI]: F := numeric::fft(L)
To use exact arithmetic, specify the option
F := numeric::fft(L, Symbolic)
numeric::fft accepts symbolic expressions.
Internally, the default method
< 16) fails because of the symbolic parameter
The following results are computed with the software arithmetic provided
by the MuPAD® kernel:
L := [x, 2, 3, x]: numeric::fft(L)
delete L, F
Compute the following multidimensional transformations. First, compute a two-dimensional transformation using an array with two indices:
A := array(1..2, 1..4, [[1, 2, 3, 4], [a, b, c, d]]): numeric::fft(A, Symbolic)
Next, compute a transformation for a three-dimensional array:
A := array(1..2, 1..4, 1..2, [[[sin(j1*PI/2)*cos(j2*3*PI/4)*sin(j3*PI/2) $ j3 = 1..2 ] $ j2 = 1..4 ] $ j1 = 1..2]): numeric::fft(A)
array(1..2, 1..4, 1..2, (1, 1, 1) = -1.0 (1, 1, 2) = -1.0 (1, 2, 1) = - 1.414213562 - 1.0 I (1, 2, 2) = - 1.414213562 - 1.0 I (1, 3, 1) = 1.0 (1, 3, 2) = 1.0 (1, 4, 1) = - 1.414213562 + 1.0 I (1, 4, 2) = - 1.414213562 + 1.0 I (2, 1, 1) = -1.0 (2, 1, 2) = -1.0 (2, 2, 1) = - 1.414213562 - 1.0 I (2, 2, 2) = - 1.414213562 - 1.0 I (2, 3, 1) = 1.0 (2, 3, 2) = 1.0 (2, 4, 1) = - 1.414213562 + 1.0 I (2, 4, 2) = - 1.414213562 + 1.0 I )
Data of arbitrary length can be transformed:
L := [1, 2 + I, PI/3]: numeric::fft(L)
One of the flags
Compared to the
If the result cannot be computed with hardware floating-point values, software arithmetic by the MuPAD kernel is tried.
If the current value of
There can be several reasons for hardware arithmetic to fail:
The trailing digits in floating-point results computed with
This option prevents conversion of the input data to floating-point values.
Without this option, the floating-point converter
Option, specified as
This option determines the domain type
If no return type is specified by this option, the result if of the same type and format as the input data.
If the return type
Reduce roundoff garbage in the result. All entries of the result
with absolute values smaller than
This option is ignored when used in conjunction with the option
List, array, hfarray, or matrix of the same length and format
as the first input parameter
M, respectively. The type of the return value
can be changed with the option