Scilab Function

fft - fast Fourier transform.

### Calling Sequence

  `[x]=fft(a,-1)`
  `[x]=fft(a,1)`
  `x=fft(a,-1,dim,incr)`
  `x=fft(a,1,dim,incr)`

### Parameters

- `x` : real or complex vector. Real or complex matrix (2-dim fft)
- `a` : real or complex vector.
- `dim` : integer
- `incr` : integer

### Description

Short syntax (one or two dimensional fft):

gives a direct transform (the `-1` refers to the sign of the exponent..., NOT to "inverse"), that is

x(k)=sum over m from 1 to n of a(m)*exp(-2i*pi*(m-1)*(k-1)/n)

for k varying from 1 to n (n=size of vector `a`).

performs the inverse transform normalized by `1/n`.

(`fft(fft(.,-1),1)` is identity).

When the first argument given to `fft` is a matrix a two-dimensional FFT is performed.

Long syntax (multidimensional FFT):

allows to perform an multidimensional fft.

If a is a real or complex vector implicitly indexed by `x1,x2,..,xp` i.e. `a(x1,x2,..,xp)` where `x`1 lies in `1..dim1,` `x2` in `1.. dim2,...` one gets a p-dimensional FFT p by calling p times `fft` as follows

     a1=fft(a ,-1,dim1,incr1)
     a2=fft(a1,-1,dim2,incr2) ...

where `dimi` is the dimension of the current variable w.r.t which one is integrating and incri is the increment which separates two successive `xi` elements in `a`.

In particular,if `a` is an nxm matrix, `x=fft(a,-1)` is equivalent to the two instructions:

`a1=fft(a,-1,m,1)` and `x=fft(a1,-1,n,m)`.

if a is an hypermatrix (see hypermat) fft(a,flag) performs the N dimensional fft of a.

### Examples

    a=[1;2;3];n=size(a,'*');
    norm(1/n*exp(2*%i*%pi*(0:n-1)'.*.(0:n-1)/n)*a -fft(a,1))
    norm(exp(-2*%i*%pi*(0:n-1)'.*.(0:n-1)/n)*a -fft(a,-1))

### See Also

`corr`