Previous Page Next Page Contents

numeric::fft, numeric::invfft -- Fast Fourier Transform

Introduction

numeric::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>)

Parameters

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.

Options

Symbolic - Without this option the floating point converter float is applied to all input data. Use this option if no such conversion is desired.

Returns

a list/array of the same length/format as the first input parameter L/A.

Side Effects

Without the option Symbolic the function is sensitive to the environment variable DIGITS, which determines the numerical working precision.

Details

Example 1

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:

Example 2

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:

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000