Accelerating the pace of engineering and science

# Documentation Center

• Trial Software

### Contents

• Examples and How To
• Concepts

# numeric::fft

Fast Fourier Transform

### Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

## Syntax

```numeric::fft(L, <mode>, <ReturnType = t>, <Clean>)
numeric::fft(M, <mode>, <ReturnType = t>, <Clean>)
numeric::fft(A, <mode>, <ReturnType = t>, <Clean>)
```

## Description

numeric::fft(data) returns the discrete Fourier transform of the data.

The 1-dimensional discrete Fourier transform F = fft(L) of N data elements Lj stored in the list L = [L1, …, LN] is the list F = [F1, …, FN] given by

.

fft transforms the data by a Fast Fourier Transform (FFT) algorithm.

The d-dimensional discrete Fourier transform F = fft(A) of N = n1×···×nd data elements (Aj1, …, jd) stored in the array A is the array F = (Fk1, …, kd) given by

with k1 = 1, …, n1, …, kd = 1, …, nd.

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 = pq, 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.

 Note:   More generally, FFT is efficient, if the data size is the product of many small factors!

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.

## Environment Interactions

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

## Examples

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

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

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

### Example 3

Data of arbitrary length can be transformed:

```L := [1, 2 + I, PI/3]:
numeric::fft(L)```

`delete L:`

## Parameters

 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

## Options

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

• The current value of DIGITS is larger than 15.

• The data contains symbolic objects.

• The data contains numbers larger than 10308 or smaller than 10- 308 that cannot be represented by hardware floats.

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 n1×n2 matrix is entered, the return value is a list with n1n2 values representing the entries of a n1×n2 matrix. The first n2 entries of the list represent the first row of the result, the next n2 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.

 Note:   The postprocessing of the result is done on the software float level. When using hardware floats, this option may increase the runtime significantly!

This option is ignored when used in conjunction with the option Symbolic.

## Return Values

List/array/hfarray/matrix of the same length and format as the first input parameter L/A/M. The type of the return value can be changed with the option ReturnType.