2D FFT中的3D FFT分解

Question

基本上，我正在使用FFT在三维中解决扩散方程，并且其中一种并行化方法是将3D FFT分解为2D FFT。

如此论文所述：https://cmb.ornl.gov/members/z8g/csproject-report.pdf 分解3D FFT的方法是：

在xy方向进行2D FFT 全局转置 在z方向进行1D FFT

我的问题是，我不确定如何进行这个全局转置（因为我认为它是转置一个3D数组）。有人遇到过这个问题吗？非常感谢。

- largelawofstrongnumbers

---

我正在使用C++和CUDA，并使用MPI进行并行化。 - largelawofstrongnumbers

问题是“我到底该怎么做？”还是“我该如何在特定平台上高效地完成它？” - Oliver Charlesworth

问题是我怎么做这个；我很难理解什么是三维矩阵转置的定义。 - largelawofstrongnumbers

Answer 1

考虑一个具有 nx*ny*nz 个元素的三维立方体。这些元素的三维FFT在数学上是沿着每个轴的一维FFT的三个阶段：

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

更普遍地，N维FFT（N>1）由许多沿该轴的（N-1）维FFT组成。

如果信号是实数，并且您有一个可以返回半频谱的FFT，则第1阶段将大约便宜一半（实FFT更便宜），其余阶段需要是复杂的，但只需要进行约一半的变换。因此，成本大约减少了一半。

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

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

P.S. 当我需要获得更高维度的心理图像时，我会想到：有数字矩阵的纸张（2D），在编号文件夹中的纸张（3D），在编号文件柜中（4D），在编号房间中（5D），在编号建筑物中（6D），等等……这样我就可以想象“文件柜”维度。

- Mark Borgerding

---

假设我们可以进行二维快速傅里叶变换。我们在原始数据上沿着z轴做xy平面，沿着y轴做zx平面，沿着x轴做yz平面。然后我们对这些结果该怎么处理呢？ - DuckQueen

你可以对一组平面执行2D FFT，然后在剩余的维度中对每个点执行1D FFT。 - Mark Borgerding

Answer 2

在论文中提到的“全局置换”不是一种数学运算，而是在分布式内存机器之间重新排列数据。第一步中在一个机器上计算的数据必须传输到所有其他机器，反之亦然，第二步也是如此。这与矩阵转置无关。

- zonksoft