function y = IFFT(x)
%
% perform inverse FFT
% written by Ming Gu for Math 128B, Spring 2009
% we assume on input the dimension of x 
% is a power of 2.
%
n = size(x,1);
if (n==1)
    y = x;
    return;
end
if (n==2)
    y = [x(1,:)+x(2,:);x(1,:)-x(2,:)];
    return;
end 
m = n/2;
z = zeros(n,size(x,2));
z(1:m,:)   = IFFT(x(2*(1:m),:));
z(m+1:n,:) = IFFT(x(1+2*(0:m-1),:));
y        = zeros(n,size(x,2));
z(1:m,:) = z(1:m,:) .* repmat(exp((-2*pi*sqrt(-1)/n)*(0:m-1)'),1,size(y,2));
y(1:m,:) = z(m+1:n,:)+z(1:m,:);
y(m+1:n,:) = z(m+1:n,:)-z(1:m,:);