2D FFT中的3D FFT分解

Question

基本上我使用FFT解决3D中的扩散方程,其中一种并行方法是在2D FFT中分解3D FFT.

如本文所述:https://cmb.ornl.gov/members/z8g/csproject-report.pdf

分解3d fft的方法是:

在xy方向上的2d fft在z方向上全局移位1d fft

基本上,我的问题是我不知道如何进行这种全局转置(因为我认为它是转换我假设的3d数组).有没有人来过这个？非常感谢.

Answer 1

想象与nx*ny*nz元素的一个3d立方体.这些元素的三维FFT在数学上是3阶段的1-d FFT,每个轴一个:

1. ny*nz沿X轴变换,每个变换处理nx个元素
2. nx*nz沿Y轴变换
3. nx*ny沿Z轴变换

更一般地,N维FFT(N> 1)由沿该轴的许多(N-1)维FFT组成.

如果信号是真实的并且你有一个可以返回半频谱的FFT,那么第1阶段的成本大约是一半(真正的FFT更便宜),其余阶段需要很复杂,但它们只需要大约一半许多转变.所以成本大约是一半.

如果您的1d FFT可以读取跨步的输入元素并将输出打包到连续的缓冲区中,那么您最终会在每个阶段进行转置.

这就是Kissfft执行多维FFT的方式.

PS当我需要获得更高尺寸的精神图片时,我想到:带有数字矩阵(2d)的纸张,带编号纸张(3d)的文件夹,带编号的文件柜(4d),带编号的房间(5d) ),在编号的建筑物(6d),等等......所以我可以想象"文件柜"的尺寸