Documentation |
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 1-dimensional 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 d-dimensional 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 1-dimensional arrays or hfarrays are transformed according to the 1-dimensional transform. Data provided by matrices are transformed according to the 2-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 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.
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.
We give a demonstration of 1-dimensional 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 multi-dimensional transformations. First, a 2-dimensional 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 3-dimensional 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:
L |
A list or a 1-dimensional array(1 .. N, [Symbol::hellip]) or a 1-dimensional hfarray(1 .. N, [Symbol::hellip]) of arithmetical expressions. |
M |
A matrix of category Cat::Matrix of arithmetical expressions. |
A |
A d-dimensional array( 1..n_1,Symbol::hellip,1..n_d, [Symbol::hellip] ) or a d-dimensional hfarray( 1..n_1,Symbol::hellip,1..n_d, [Symbol::hellip] ) of arithmetical expressions. |
mode |
One of the flags Hard, HardwareFloats, Soft, SoftwareFloats, or Symbolic |
Hard, HardwareFloats, Soft, SoftwareFloats |
With Hard (or HardwareFloats), computations are done using fast hardware float arithmetic from within a MuPAD session. Hard and HardwareFloats are equivalent. With this option, the input data are converted to hardware floats and processed by compiled C code. The result is reconverted to MuPAD floats and returned to the MuPAD session. With Soft (or SoftwareFloats) computations are dome using software float arithmetic provided by the MuPAD kernel. Soft and SoftwareFloats are equivalent. SoftwareFloats is used by default if the current value of DIGITS is larger than 15 and the input matrix A is not of domain type DOM_HFARRAY. Compared to the SoftwareFloats used by the MuPAD kernel, the computation with HardwareFloats may be many times faster. Note, however, that the precision of hardware arithmetic is limited to about 15 digits. Further, the size of floating-point numbers may not be larger than approximately 10^{308} and not smaller than approximately 10^{- 308}. If no HardwareFloats or SoftwareFloats are requested explicitly, the following strategy is used: If the current value of DIGITS is smaller than 16 or if the matrix A is a hardware float array of domain type DOM_HFARRAY, then hardware arithmetic is tried. If this is successful, the result is returned. If the result cannot be computed with hardware floats, software arithmetic by the MuPAD kernel is tried. If the current value of DIGITS is larger than 15 and the input matrix A is not of domain type DOM_HFARRAY, or if one of the options Soft, SoftwareFloats or Symbolic is specified, MuPAD computes the result with its software arithmetic without trying to use hardware floats first. There may be several reasons for hardware arithmetic to fail:
If neither HardwareFloats nor SoftwareFloats is specified, the user is not informed whether hardware floats or software floats are used. If HardwareFloats are specified but fail due to one of the reasons above, a warning is issued that the (much slower) software floating-point arithmetic of the MuPAD kernel is used. Note that HardwareFloats can only be used if all input data can be converted to floating-point numbers. With Soft and SoftwareFloats, symbolic objects are accepted even if they cannot be converted to floating-point numbers. The result consists of arithmetical expressions involving both floating-point numbers as well as symbolic objects. See. Example 1. The trailing digits in floating-point results computed with HardwareFloats and SoftwareFloats may differ. | |
Symbolic |
Without this option, the floating-point converter float is applied to all input data. Use this option if no such conversion is desired. Exact arithmetic is used to compute the Fourier transformation. This option prevents conversion of the input data to floats. | |
ReturnType |
Option, specified as ReturnType = t Return the result in a container of domain type t. The following return types t are available: DOM_LIST, or DOM_ARRAY, or DOM_HFARRAY, or matrix, or densematrix. This option determines the domain type t of the result. 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 DOM_LIST is specified, the result is always a plain list of floating-point numbers. If the input data are given by a matrix or a multi-dimensional array, the returned list represents the operands of the multi-dimensional Fourier data. E.g., if an n_{1}×n_{2} matrix is entered, the return value is a list with n_{1} n_{2} values representing the entries of a n_{1}×n_{2} matrix. The first n_{2} entries of the list represent the first row of the result, the next n_{2} entries represent the second row, etc. With ReturnType = matrix or ReturnType = densematrix, only the results of 1 and 2 dimensional Fourier transformations can be represented. | |
Clean |
Reduce roundoff garbage in the result. All entries of the result with absolute values smaller than 10^(-DIGITS) times the maximal absolute value of all operands of the result are set to 0.0. Further, the routine numeric::complexRound is applied to all entries of the result.
This option is ignored when used in conjunction with the option Symbolic. |