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

6 次查看（过去 30 天）
Thomas Barrett
Thomas Barrett 2021-7-23
编辑： Matt J 2021-7-27
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 个评论
显示 3更早的评论
Matt J
Matt J 2021-7-27
编辑：Matt J 2021-7-27
Ran in:
That's almost what I mean. It's not the reshape() that is costing you time. It is the permute(). There is no need to permute that I can see. You could just as easily do,
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);
end
toc
Elapsed time is 3.544917 seconds.
and we can see below that the time spent is essentially the same time as if only the fftn() operation is included:
B= reshape( A0, [Nz,Ny,Nx] ) ;
tic
for k = 1:20
A_3D = fftn(B);
end
toc
Elapsed time is 3.483294 seconds.
Thomas Barrett
Thomas Barrett 2021-7-27
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?

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2021-7-27
编辑：Matt J 2021-7-27
Ran in:
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.

更多回答（1 个）

rajmouli jujjavarapu
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 个评论
显示 2更早的评论
Thomas Barrett
Thomas Barrett 2021-7-23
编辑：Thomas Barrett 2021-7-23
For sure the output of the FFT of the 1D vector will be another 1D vector - this I am happy with. But it should not simply be a direct 1D FFT of that vector (it should somehow account for the fact that this is a linearised 3D matrix). And yes, it can certainly be done by reshaping before using fftn and then reshape back after, but this is computationally costly, and I would like to avoid it.
rajmouli jujjavarapu
rajmouli jujjavarapu 2021-7-23
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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Fourier Analysis and Filtering 的更多信息

标签

产品


版本

R2017a

Community Treasure Hunt

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

Start Hunting!

Translated by