Fast Fourier transform

computes
the discrete
Fourier transform (DFT) of `Y`

= fft(`X`

)`X`

using a fast
Fourier transform (FFT) algorithm.

If

`X`

is a vector, then`fft(X)`

returns the Fourier transform of the vector.If

`X`

is a matrix, then`fft(X)`

treats the columns of`X`

as vectors and returns the Fourier transform of each column.If

`X`

is a multidimensional array, then`fft(X)`

treats the values along the first array dimension whose size does not equal 1 as vectors and returns the Fourier transform of each vector.

returns
the `Y`

= fft(`X`

,`n`

)`n`

-point DFT. If no value is specified, `Y`

is
the same size as `X`

.

If

`X`

is a vector and the length of`X`

is less than`n`

, then`X`

is padded with trailing zeros to length`n`

.If

`X`

is a vector and the length of`X`

is greater than`n`

, then`X`

is truncated to length`n`

.If

`X`

is a matrix, then each column is treated as in the vector case.If

`X`

is a multidimensional array, then the first array dimension whose size does not equal 1 is treated as in the vector case.

The execution time for

`fft`

depends on the length of the transform. Transform lengths that have only small prime factors are significantly faster than those that are prime or have large prime factors.For most values of

`n`

, real-input DFTs require roughly half the computation time of complex-input DFTs. However, when`n`

has large prime factors, there is little or no speed difference.You can potentially increase the speed of

`fft`

using the utility function,`fftw`

. This function controls the optimization of the algorithm used to compute an FFT of a particular size and dimension.

The FFT functions (`fft`

, `fft2`

, `fftn`

, `ifft`

, `ifft2`

, `ifftn`

)
are based on a library called FFTW [1] [2].

[1] FFTW (http://www.fftw.org)

[2] Frigo, M., and S. G. Johnson. “FFTW:
An Adaptive Software Architecture for the FFT.” *Proceedings
of the International Conference on Acoustics, Speech, and Signal
Processing*. Vol. 3, 1998, pp. 1381-1384.