# fft

Direct or inverse Fast Fourier Transform of a vector, matrix, or hypermatrix

# ifft

Inverse fast Fourier transform.

### Syntax

X = fft(A)
X = fft(A, sign)
X = fft(A, sign, directions)
X = fft(A, sign, dims, incr)
X = fft(.., symmetry)

### Arguments

A, X
vectors, matrices or ND-arrays of real or complex numbers, of same sizes.

sign
-1 or 1 : sign of the ±2iπ factor in the exponential term of the transform formula, setting the direct or inverse transform. The default value is -1 = Direct transform.

directions
vector containing indices of A dimensions (in [1, ndims(A)]) along which the (multidirectional) FFT must be computed. Default directions=1:ndims(A): The "cumulated" FFT is computed for all directions. See the Description section.

symmetry
optional character string, helping fft() to choose the best algorithm:
• "symmetric": forces to consider A or all its "slices" as conjugate symmetric. This is useful when an exact symmetry of A or its "slices" is possibly altered only by round-off errors.

A ND-array B of sizes [s1,s2,..,sN] is conjugate symmetric for the FFT if and only if B==conj(B([1 s1:-1:2],[1 s2:-1:2],...,[1 sN:-1:2])). In such a case, the result X is real, and an efficient specific algorithm can be used to compute it.

• "nonsymmetric": Then fft() does not take care of any symmetry.

• not specified: Then an automatic determination of symmetry is performed.

dims
vector of positive integers. Old syntax. Each element must be a divisor of length(A). The product of the elements must be strictly smaller than length(A). See the Description section for details.

incr
vector of positive strictly increasing integers, as long as dims. Old syntax. Each element must be a divisor of length(A). See the Description section for details.

### Description

This function computes the direct or inverse 1D, 2D, or.. ND Discrete Fourier Transform of an array or ND-array of numbers, along one or several directions inside this one.

##### Short syntax

Direct transform:

X = fft(A [,symmetry]) or X = fft(A, -1 [,symmetry]) gives a direct transform.

single variate
a=A is a vector: a single variate direct FFT is computed, that is:

multivariate
A is a matrix or a multidimensional array: A multivariate direct FFT is performed.

Inverse normalized transform:

X = fft(A,+1) or X = ifft(A) performs the inverse normalized transform, such that A==ifft(fft(A)).

single variate
a=A is a vector: X = fft(a, +1) or X = ifft(a) perform a single variate inverse FFT, computed as

multivariate
A is a matrix or a multidimensional array: A multivariate inverse FFT is performed.

##### Long syntax : Multidimensionnal directional FFT

X = fft(A, sign, directions [, symmetry]) performs efficiently all direct or inverse FFT of all "slices" of A along selected directions.

For example, if A is a 3D array, X = fft(A,-1,2) is equivalent to:

for i1 = 1:size(A,1)
for i3 = 1:size(A,3)
X(i1,:,i3) = fft(A(i1,:,i3), -1);
end
end

and X = fft(A,-1,[1 3]) is equivalent to:

for i2 = 1:size(A,2)
X(:,i2,:) = fft(A(:,i2,:), -1);
end

X = fft(A, sign, dims, incr [, symmetry]) is an old syntax that also allows to perform all direct or inverse FFT of the slices of A along selected directions. With this syntax, A is considered as serialized into a vector, and its actual sizes are ignored. The slices are selected by providing A sizes and increments of the serialized index, related to dimensions.

For example, if A is an array with n1*n2*n3 elements, X = fft(A,-1, n1, 1) is equivalent to X = fft(matrix(A,[n1,n2,n3]), -1, 1) ; and X = fft(A,-1, [n1 n3], [1 n1*n2]) is equivalent to X = fft(matrix(A,[n1,n2,n3]), -1, [1,3]).

##### Optimizing fft

Remark: The fft() function automatically stores its last internal parameters in memory to re-use them in a second time. This improves greatly the time computation when consecutive calls (with same parameters) are performed.

It is possible to go further in fft() optimization using the get_fftw_wisdom and set_fftw_wisdom functions.

Algorithms: fft() uses the fftw3 library.

Bibliography: Matteo Frigo and Steven G. Johnson, "FFTW Documentation" http://www.fftw.org/#documentation

### Examples

1D FFT (of a vector):

//Frequency components of a signal
//----------------------------------
// build a noised signal sampled at 1000hz  containing  pure frequencies
// at 50 and 70 Hz
sample_rate = 1000;
t = 0:1/sample_rate:0.6;
N = size(t,'*'); //number of samples
s = sin(2*%pi*50*t) + sin(2*%pi*70*t+%pi/4) + grand(1,N,'nor',0,1);

y=fft(s);

// s is real so the fft response is conjugate symmetric and we retain only the first N/2 points
f = sample_rate*(0:(N/2))/N; //associated frequency vector
n = size(f,'*')
clf()
plot(f, abs(y(1:n)))

2D FFT (of a matrix):

A = zeros(256,256);
A(5:24,13:17) = 1;
X = fftshift(fft(A));
set(gcf(), "color_map",jetcolormap(128));
clf; grayplot(0:255, 0:255, abs(X)')

N-Dimensional FFT (of a ND array):

// simple case, 3 1-D fft at a time
N = 2048;
t = linspace(0,10,2048);
A = [2*sin(2*%pi*3*t) + sin(2*%pi*3.5*t)
10*sin(2*%pi*8*t)
sin(2*%pi*0.5*t) + 4*sin(2*%pi*0.8*t)];
X = fft(A,-1,2);

fs = 1/(t(2)-t(1));
f = fs*(0:(N/2))/N; // associated frequency vector
clf; plot(f(1:100)',abs(X(:,1:100))')
legend(["3 and 3.5 Hz","8 Hz","0.5 and 0.8 Hz"],"in_upper_left")

// 45  3-D fft at a time
Dims = [5 4 9 5 6];
A = matrix(rand(1, prod(Dims)), Dims);

y = fft(A,-1,[2 4 5]);

// equivalent (but less efficient code)
y1 = zeros(A);
for i1 = 1:Dims(1)
for i3 = 1:Dims(3)
ind = list(i1,:,i3,:,:);
y1(ind(:)) = fft(A(ind(:)),-1);
end
end
// Using explicit formula for  1-D discrete Fourier transform
// ----------------------------------------------------------
function xf=DFT(x, Sign);
n = size(x,'*');
// Compute the n by n Fourier matrix
am = exp(Sign * 2*%pi*%i * (0:n-1)'*(0:n-1)/n);
xf = am * matrix(x,n,1);  // dft
xf = matrix(xf,size(x));  // reshape
if Sign == 1 then
xf = xf/n;
end
endfunction

// Comparison with the fast Fourier algorithm
a = rand(1,1000);
norm(DFT(a,1) - fft(a,1))
norm(DFT(a,-1) - fft(a,-1))

tic(); DFT(a,-1); toc()
tic(); fft(a,-1); toc()