numeric::fft, numeric::invfft
--
Fast Fourier Transformnumeric::fft
(data, ..)
returns the
discrete Fourier transform of the data
.
numeric::invfft
(data, ..)
returns the
inverse discrete Fourier transform.
numeric::fft(L <, Symbolic>)
numeric::fft(A <, Symbolic>)
numeric::invfft(L <, Symbolic>)
numeric::invfft(A <, Symbolic>)
L |
- | a list of arithmetical expressions. The length of the list must be an integer power of 2. |
A |
- | a d-dimensional array(1..n[1], .. , 1..n[d], [..]) of arithmetical expressions. The values n[1],..,n[d] must all be integer powers of 2. |
Symbolic |
- | Without this option the floating point converter
float is applied to all
input data. Use this option if no such conversion is desired. |
a list/array of the same length/format as the first input parameter
L
/A
.
Without the option Symbolic the function is
sensitive to the environment variable DIGITS
, which determines the
numerical working precision.
F[k] = sum(L[j]*exp(-2*PI*I*(j-1)*(k-1)/N), j=1..N), k = 1,..,N.The inverse transformation L=invfft(F) is given by
L[j] = 1/N * sum(F[k]*exp(2*PI*I(j-1)*(k-1)/N), k=1..N), j = 1,..,N.
fft
and invfft
transform the data by the Fast
Fourier Transform (FFT) algorithm with O(N*log(2,N))
operations.F[k[1],..,k[d]] = sum( .. (sum( A[j[1],..,j[d]] * exp(-2*PI*I*((j[1]-1)*(k[1]-1)*/n[1]+ .. +(j[d]-1)*(k[d]-1)/n[d]), j[d]=1..n[d]), .. ,j[1]=1..n[1])with k[1] = 1,..,n[1], .. , k[d] = 1,..,n[d]. The inverse transformation A=invfft(F) is given by
A[j[1],..,j[d]] = 1/N * sum( .. (sum( F[k[1],..,k[d]] * exp(2*PI*I*((j[1]-1)*(k[1]-1)*/n[1]+ .. +(j[d]-1)*(k[d]-1)/n[d]), k[d]=1..n[d]), .. ,k[1]=1..n[1])with j[1] = 1,..,n[1], .. , j[d] = 1,..,n[d].
fft
and invfft
transform the data by the Fast
Fourier Transform (FFT) algorithm with O(N*log(2,N))
operations.We give a demonstration of 1-dimensional transformations using lists. By default, numerical expressions are converted to floats:
>> L := [1, 2^(1/2), 3, PI]: numeric::fft(L)
[8.555806216, - 2.0 + 1.727379091 I, -0.5558062159, - 2.0 - 1.727379091 I]
>> numeric::invfft(%)
[1.0, 1.414213562 - 1.084202173e-19 I, 3.0, 3.141592654 + 1.084202173e-19 I]
Exact arithmetic is used with the option Symbolic:
>> numeric::fft(L, Symbolic)
1/2 1/2 1/2 [PI + 2 + 4, I PI - I 2 - 2, 4 - 2 - PI, 1/2 I 2 - I PI - 2]
>> numeric::invfft(%, Symbolic)
1/2 [1, 2 , 3, PI]
Symbolic expressions are accepted:
>> L := [x, 2, 3, x]: numeric::fft(L)
[2 x + 5.0, (1.0 + 1.0 I) x - (3.0 + 2.0 I), 1.0, (1.0 - 1.0 I) x - (3.0 - 2.0 I)]
>> numeric::fft(L, Symbolic)
[2 x + 5, (1 + I) x - (3 + 2 I), 1, (1 - I) x - (3 - 2 I)]
>> delete L:
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)
array(1..2, 1..4, (1, 1) = a + b + c + d + 10, (1, 2) = a - I b - c + I d - (2 - 2 I), (1, 3) = a - b + c - d - 2, (1, 4) = a + I b - c - I d - (2 + 2 I), (2, 1) = 10 - b - c - d - a, (2, 2) = I b - a + c - I d - (2 - 2 I), (2, 3) = b - a - c + d - 2, (2, 4) = c - I b - a + I d - (2 + 2 I) )
>> numeric::invfft(%, Symbolic)
+- -+ | 1, 2, 3, 4 | | | | a, b, c, d | +- -+
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:
fft
and
ifft
, respectively, in previous MuPAD
versions.