## `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

- 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

      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.
- The d-dimensional discrete Fourier transform F=fft(A) of N = n[1]*..*n[d] data elements (A[j[1],..,j[d]]) stored in the array A is the array F = (F[k[1],..,k[d]]) given by

              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 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

- These functions used to be called `fft` and `ifft`, respectively, in previous MuPAD versions.
- The length of input lists needs not be specified by a second parameter any more.
- Multi-dimensional transformations are now possible by using appropriately formatted input arrays
- .
- The option Symbolic was added.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000