Fast Fourier Transform
This functionality does not run in MATLAB.
numeric::fft(L
, <mode
>, <ReturnType = t
>, <Clean
>) numeric::fft(M
, <mode
>, <ReturnType = t
>, <Clean
>) numeric::fft(A
, <mode
>, <ReturnType = t
>, <Clean
>)
numeric::fft(data)
returns the discrete Fourier
transform of the data
.
The 1dimensional discrete Fourier transform F = fft(L) of N data elements L_{j} stored in the list L = [L_{1}, …, L_{N}] is the list F = [F_{1}, …, F_{N}] given by
.
fft
transforms the data by a Fast Fourier
Transform (FFT) algorithm.
The ddimensional discrete Fourier transform F = fft(A) of N = n_{1}×···×n_{d} data elements (A_{j1, …, jd}) stored in the array A is the array F = (F_{k1, …, kd}) given by
with k_{1} = 1, …, n_{1}, …, k_{d} = 1, …, n_{d}.
Data provided by lists or 1dimensional array
s or hfarray
s are transformed according to
the 1dimensional transform. Data provided by matrices are transformed
according to the 2dimensional transform. Data provided by multidimensional
arrays or hfarrays are transformed according to the multidimensional
transform matching the format of the input array.
If the data size factorizes (N = p q,
say), 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
elementary
operations.
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 zeropadded 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.
We give a demonstration of 1dimensional transformations using lists. By default, numerical expressions are converted to floats:
L := [1, 2^(1/2), 3*I, PI]: F := numeric::fft(L)
numeric::invfft(F)
numeric::invfft(F, Clean)
Exact arithmetic is used with the option Symbolic
:
F := numeric::fft(L, Symbolic)
numeric::invfft(F, Symbolic)
Symbolic expressions are accepted. Internally, however, the
default method HardwareFloats
(with DIGITS
< 16
) fails because of the symbolic parameter x
.
The following results are computed with the software arithmetic provided
by the MuPAD^{®} kernel:
L := [x, 2, 3, x]: numeric::fft(L)
numeric::fft(L, Symbolic)
delete L, F:
We give a demonstration of multidimensional transformations. First, a 2dimensional transformation is computed by using an array with 2 indices:
A := array(1..2, 1..4, [[1, 2, 3, 4], [a, b, c, d]]): numeric::fft(A, Symbolic)
numeric::invfft(%, Symbolic)
The next example is 3dimensional as indicated by the format of the 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 )
delete A:
Data of arbitrary length can be transformed:
L := [1, 2 + I, PI/3]: numeric::fft(L)
delete L:

A list or a 1dimensional array( 

A 

A ddimensional 

One of the flags 

With With Compared to the If no If the result cannot be computed with hardware floats, software arithmetic by the MuPAD kernel is tried. If the current value of There may be several reasons for hardware arithmetic to fail:
If neither If Note that With The trailing digits in floatingpoint results computed with  

Without this option, the floatingpoint converter This option prevents conversion of the input data to floats.  

Option, specified as Return the result in a container of domain type 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 With  

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/matrix of the same length and format as the
first input parameter L
/A
/M
.
The type of the return value can be changed with the option ReturnType
.