Ciculant Matrices and FFT

contents

ටcirculant matrix
ටfast fourier transform
ටconnection of FFT and circulant matrix
ටproblem
ටsolution
ටresources

ciculant matrix

A circulant matrix can be seen as vector of length N, the size of N being defined by the owner of the vector. The special thing about the vector is that it permits an operation that after performing it on the vector of length N you are left with a reordering of the data in such a way that it represents a circulant matrix structure. Here the operation is right shift to the vector 1 unit. The last element replaces the first element and this is repeated N times.

A := Matrix(N, N);

for i=1 to N do

 A[i,j] := Rotate(U, -(i-1));

end do

return A

Image

After this operation is performed on the vector the new structure leaves it with special properties. In this case the data has been normalized. This means it can commute with other circulant matrices allowing you to compute on them the same as you would with two single numbers. One of the important things included in being able to treat matrices as numbers is having an inverse and this operation supplies us with one.

With this structure obtained there is many applications, the shifting is a good representation of a time series or any sequential events. Examples could be shifting of geometric shapes and signal proccessing.

fast fourier transform

The Fourier transform is another operation on a vector. This is similar to the circulant operation in that it takes in data of a specified size and structure and returns you data of the same specified size and structure. Our specified size here is a vector of length N.

for k to col_length do

 for n to row_length do

  X[k] += x[n]*exp(((-2*pi)*(I)*(k-1)*(n-1))/(N));

 end do;

end do;

Image

Above is the formula for the DFT the discrete fourier transform. The fast fourier transform is a reordering of the operations from the DFT taking advantage of known structure to reduce the computation time. The first most important structure we know of is even and odd. To impose this we restrict our length of the vector to be 2^N. The vector is labeled from [0 ... N-1], with this smooth sequence we get from labelling the non smooth sequence we can split it up into n=0 from [(2n+1) ... N-1] and n=0 from [2n ... N-1]. Visually splitting up looks like the picture below.

for n=0 to N/2 do

 X[2(n)] += x[2*n]*exp(((-2*pi)*(I)*(n)*(n))/(N/2));

end do;

for n=0 to N/2 do

 X[2(n)+1] += x[n]*x[(2*n)+1]*exp(((-2*pi)*(I)*(n)*(n))/(N/2));

end do;

Image

The interesting thing about this is you can see in the picture above the index of the element position in the array is changing but the size of the array is not changing, then computation is carried out. Becasue of the base 2 of machine numbers the bits can be reversed to accomplish that index changing. This as well as the symmetry is a big reason why the FFT is so fast

One way of looking at it is you have one large matrix of length N and you split it into two smaller of size N/2. You then can apply the same operation to these two smaller matrices which ends up splitting the total operations from 2N to just N. Or 2 loops of equal size to just one loop of that size. Instead of loops you can perform matrix multiplication. On parallel computer architecture you can then run these matrix multiplications at the same time. This can then be split in many ways like 2, 4, 8, 16, ... 2N or interms of prime numbers 1, 3, 5, 7 , ...