# fft

Fast Fourier transform

## Description

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.

## Examples

## Input Arguments

## Output Arguments

## More About

## Tips

The execution time of

`fft`

depends on the length of the transform. Transform lengths that have only small prime factors (not greater than 7) result in significantly faster execution time 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.

## Algorithms

The FFT functions (`fft`

, `fft2`

,
`fftn`

, `ifft`

, `ifft2`

,
`ifftn`

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

## References

[1] FFTW (https://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.

## Extended Capabilities

## Version History

**Introduced before R2006a**