Is it possible to correctly perform a multi-dimensional FFT on a 1D linearised version of a 3D array?

3 views (last 30 days)
Thomas Barrett
Thomas Barrett on 23 Jul 2021
Edited: Matt J on 27 Jul 2021
I have a 3D array indexed by A_3D(ind_y,ind_x,ind_z). This has then been converted to a single 1D linear vector B_1D(ind) such that the coordinates cycle through the z coorindinates fastest, followed by y, and finally by x which is the slowest to increment.
I am able to take the FFT of the 3D matrix A_3D no problem, using fftn(). I would like to know if it is possible in Matlab to successfully take a FFT of B_1D directly. In other words, is it possible to do a multi-dimensional FFT when working with a linearised 3D array?
My attempt below fails, because when calling fft() it simply takes a 1D FFT of the entire vector, not caring that there are blocks of points which correspond to different dimensions:
Nx = 3;
Ny = 2;
Nz = 4;
N = Nx*Ny*Nz;
[X , Y , Z] = meshgrid(1:Nx,1:Ny,1:Nz);
%%% Do the FFT on a 3D matrix, and reshape the output to 1D vector
A_3D = rand(size(X)); % Create random 3D matrix, indexed by A_3D(indy,indx,indz)
A_3D_FFT = fftn(A_3D); % 3D FFT
A_1D_FFT = reshape( permute(A_3D_FFT,[3,1,2]),[1 N] ); % Reshape output of FFT so cycle through z fastest, then y, then x
%%% Do FFT correctly on a reshaped, 1D version of the original 3D array?
B_1D = reshape( permute(A_3D,[3,1,2]),[1 N] ); % Instead of reshaping output of FFT, reshape original matrix instead
B_1D_FFT = fftn(B_1D, [Ny,Nx,Nz]); % Is there a way to do this, even though B_1D has been flattened?
max( abs(A_1D_FFT - B_1D_FFT) ) % Check if equivalent
I know that this is possible in C++, because in the FFTW library help docs you can specify a "FFT plan" for fftwnd using
my_plan = fftw3d_create_plan_specific(Nx,Ny,Nz,...
which gives information about how the initial 3D matrix was unwrapped to 1D. Then you can do something like
B_1D_FFT = fftwnd(my_plan , 1 , B_1D , 1 , Nx*Ny*Nz , ... );
and in this case the transform is done correctly. I would like to do the same thing in Matlab (which I believe is based on the same fftw library)
  5 Comments
Thomas Barrett
Thomas Barrett on 27 Jul 2021
Great, thanks @Matt J you are totally right - there was no need to permute, since it was being undone again. I didn't realise that permute was so intensive, and that reshape was so efficient.
I was originally interested in whether Matlab allows access to some of the other fftw features (such as "plans", etc), but doing the reshape is sufficient. Do you want to add it as an answer, then I can accept it for completeness?

Sign in to comment.

Accepted Answer

Matt J
Matt J on 27 Jul 2021
Edited: Matt J on 27 Jul 2021
Reshaping to and from 3D format should not add significant cost:
Nx = 256;
Ny = 256;
Nz = 128;
N = Nx*Ny*Nz;
A0 = rand(N,1);
tic
for k = 1:20
B = reshape( A0, [Nz,Ny,Nx] ) ;
A_3D = fftn(B);
A_1D = reshape( A_3D, N,1); %Strangely, A_1D=A_3D(:) is much slower ????
end
toc
Elapsed time is 3.575770 seconds.
When compared to processing without reshaping, it is almost the same:
B= reshape( A0, [Nz,Ny,Nx] ) ;
tic
for k = 1:20
A_3D = fftn(B);
end
toc
Elapsed time is 3.422608 seconds.

More Answers (1)

rajmouli jujjavarapu
rajmouli jujjavarapu on 23 Jul 2021
F_d = fft(t_d, [], n);
At the n term if you could specify the dimension, in your case it is 3. I guess this computes each layer individually.
  4 Comments
rajmouli jujjavarapu
rajmouli jujjavarapu on 23 Jul 2021
I understand. I didnot find any function for this, but lets wait and see. somebody will have a good idea and will reply.
Thank you.

Sign in to comment.

Products


Release

R2017a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by