performance - 2D FFT 中的 3D FFT 分解

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 在数学上是 3 个阶段的 1-d FFT，沿每个轴一个：

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

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

如果信号是真实的，并且您有一个可以返回半频谱的 FFT，那么第 1 阶段的成本大约是前者的一半（真正的 FFT 更便宜），其余的阶段需要很复杂，但它们只需要大约一半许多变换。所以成本大约是一半。

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

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

PS当我需要获得更高维度的心理图片时，我会想到：带有数字矩阵的纸张（2d），编号文件的文件夹（3d），编号的文件柜（4d），编号的房间（5d） ），编号建筑物（6d），等等......所以我可以想象“文件柜”尺寸

Answer 2

论文中提到的“全局转置”不是数学运算，而是分布式内存机器之间的数据重排。

在步骤 1 中在一台机器上计算的数据必须传输到所有其他机器，反之亦然，以进行 step to。它与矩阵转置无关。