2DFFT中的3DFFT分解

Question

基本上，我使用FFT在3D中求解扩散方程，其中一种并行化的方法是将3D FFT分解为2D 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立方体。这些元素的3d FFT在数学上是1-d FFT的3个阶段，每个轴一个阶段：

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

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

如果信号是实数，并且你有一个可以返回半频谱的FFT，那么阶段1的成本大约是一半(实数FFT更便宜)，其余的阶段需要复杂，但它们只需要大约一半的变换数量。所以成本大约是一半。

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

这就是kissfft执行多维FFT的方式。

附注:当我需要获得更高维度的脑海中的图片时，我会想到:带有数字矩阵的纸张(2d)，在编号文件的文件夹中(3d)，在编号文件柜中(4d)，在编号房间(5d)，在编号建筑物(6d)，等等……所以我可以想象“文件柜”的尺寸

Answer 2

论文中提到的“全局转置”不是数学运算，而是distributed memory machines之间数据的重新排列。

对于步骤1，在一台机器上计算的数据必须传输到所有其他机器，反之亦然。它与矩阵转置没有任何关系。