计算矩阵/多维数组的FFT时为什么需要计算转置？

Question

我目前正在解决一个问题，需要使用FFTW与MPI相结合计算二维矩阵的傅里叶变换。

根据FFTW文档中的第一部分，在并行计算矩阵的傅里叶变换时，需要在启动的进程之间进行大量通信。例如，对于像下面这样的矩阵：

1,2,3
4,5,6
7,8,9

我们决定使用三个进程计算FFT，每个进程获取该矩阵的一部分，以便数据存储在每个进程的本地内存中，如P_0 [1,2,3]，P_1 [4,5,6]，P_3 [7,8,9]。

计算初始傅里叶变换后，需要进行转置，这需要在三个进程之间通信计算出的数据，如下所示：

P_0 -> P_1: 2
P_0 -> P_2: 3
P_1 -> P_0: 4
P_1 -> P_2: 6
P_2 -> P_0: 7
P_2 -> P_1: 8

由于这会产生很大的开销，因此上述FFTW文档页面的第二部分建议直接在傅里叶空间中计算转置，以大幅减少所需的跨进程通信量。

我仍然不确定为什么首先需要计算转置，并且不同块矩阵计算出的数据如何合并。为什么设置FFTW_MPI_TRANSPOSED_OUT和FFTW_MPI_TRANSPOSED_IN标志就足以不再需要来自其他进程的大量数据进行跨进程通信了？

- Yes

---

请注意，这不是必需的 - 这只是一种常见的实现方式。这里有另一种方法 - https://www.researchgate.net/publication/251555014_A_DAFT_DL_POLY1_distributed_memory_adaptation_of_the_smoothed_particle_mesh_Ewald_method - Ian Bush

Answer 1

2D FFT首先对数组的行进行1D FFT计算，然后对列进行1D FFT计算(或者反过来也可以)，文档中提到的第一次转置是为了让一个进程中的数据在一起以便进行1D FFT计算。第二次转置是为了重新排列得到正确顺序的结果数组。

step 1:
| a b c |  -> 1D FFT ->  | A B C |
| d e f |  -> 1D FFT ->  | D E F | (each row is data belonging to one process)
| g h i |  -> 1D FFT ->  | G H I |
step 2:
| A B C |  -> transpose ->  | A D G |
| D E F |  -> transpose ->  | B E H | (inter-process communication)
| G H I |  -> transpose ->  | C F I |
step 3:
| A D G |  -> 1D FFT ->  | J M P |
| B E H |  -> 1D FFT ->  | K N Q |
| C F I |  -> 1D FFT ->  | L O R |
step 4:
| J M P |  -> transpose ->  | J K L |
| K N Q |  -> transpose ->  | M N O | (the actual 2D FFT of the initial array)
| L O R |  -> transpose ->  | P Q R |

如果您满意于使用第3步的结果而非第4步，则无需进行第4步，这可以节省很多通信时间。该结果是否有用或者是否需要转置取决于应用程序，因此该库允许您进行选择。

指定输入或输出是否转置会影响传递到函数中的数组大小的顺序。在两种情况下，都会跳过最后一个转置：

请注意，FFTW_MPI_TRANSPOSED_IN与执行FFTW_MPI_TRANSPOSED_OUT并将前两个维度以相反的顺序传递给规划器（或反之亦然）完全等效。如果同时传递FFTW_MPI_TRANSPOSED_IN和FFTW_MPI_TRANSPOSED_OUT标志，则等效于交换传递给规划器的前两个维度并不传递任何标志。

不可能跳过两次转置。

例如，为了通过FFT计算卷积，我们需要将正向FFT应用于一个数组，乘以一个核，然后应用反向FFT。在这种情况下，乘法使用一个转置的数组同样有效，所以我们可以对正向FFT使用FFTW_MPI_TRANSPOSED_OUT，对反向FFT使用FFTW_MPI_TRANSPOSED_IN。最终结果与传递任何标志并让所有转置发生的结果相同，但效率更高。

- Cris Luengo