numeric::fft, numeric::invfft --
Fast Fourier Transform
Introductionnumeric::fft(data, ..) returns the
discrete Fourier transform of the data.
numeric::invfft(data, ..) returns the
inverse discrete Fourier transform.
Call(s)numeric::fft(L <, Symbolic>)
numeric::fft(A <, Symbolic>)
numeric::invfft(L <, Symbolic>)
numeric::invfft(A <, Symbolic>)
ParametersL |
- | 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. |
OptionsSymbolic |
- | Without this option the floating point converter
float is applied to all
input data. Use this option if no such conversion is desired. |
Returnsa list/array of the same length/format as the first input parameter
L/A.
Side
EffectsWithout the option Symbolic the function is
sensitive to the environment variable DIGITS, which determines the
numerical working precision.
DetailsF[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.
Example
1We 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:
Example
2We 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.