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

The one-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 a list, or one-dimensional `array`, or `hfarray` are transformed according to the one-dimensional transform. Data provided by matrices are transformed according to the twp-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 N factorizes as N = pq, 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

Compute one-dimensional transformations using lists. By default, numerical expressions are converted to floating-point values:

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

To use exact arithmetic, specify the option `Symbolic`:

`F := numeric::fft(L, Symbolic)`

`numeric::fft` accepts symbolic expressions. Internally, 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

Compute the following multidimensional transformations. First, compute a two-dimensional transformation using an array with two indices:

```A := array(1..2, 1..4, [[1, 2, 3, 4], [a, b, c, d]]): numeric::fft(A, Symbolic)```

Next, compute a transformation for a three-dimensional 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 one-dimensional array(`1 .. N, [Symbol::hellip]`), or a one-dimensional hfarray(```1 .. N, [Symbol::hellip]```) of arithmetical expressions. `M` `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 floating-point arithmetic from within a MuPAD session. `Hard` and `HardwareFloats` are equivalent. With this option, the input data are converted to hardware floating-point values and processed by compiled C code. The result is reconverted to MuPAD floating-point values and returned to the MuPAD session.

With `Soft` (or `SoftwareFloats`) computations are done using software floating-point 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` can be much faster. Note, however, that the precision of hardware arithmetic is limited to about 15 digits. Further, the size of floating-point numbers can not be larger than approximately 10308 and not smaller than approximately 10- 308.

If no `HardwareFloats` or `SoftwareFloats` are specified, the following strategy is used. If the current value of `DIGITS` is smaller than 16 or if the matrix `A` is a hardware floating-point 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 floating-point values, 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 arithmetic first.

There can 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 floating-point values.

If neither `HardwareFloats` nor `SoftwareFloats` is specified, the function does not indicate whether hardware floating-point values or software floating-point values 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` can differ.

`Symbolic`

This option prevents conversion of the input data to floating-point values.

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.

`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 multidimensional array, the returned list represents the operands of the multidimensional Fourier data. For example, 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, and so on.

With `ReturnType` = `matrix` or `ReturnType` = `densematrix`, only the results of one- and two-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 level. When using hardware floating-point values, this option can increase the runtime significantly.

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

## Return Values

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