并行计算矩阵/多维数组FFT时为何需要进行转置操作

为什么并行二维FFT流程必须执行转置，分块如何合并 #

二维FFT的计算逻辑是完全可分离的：对一个N×M矩阵做二维FFT，等价于先对矩阵的每一行做1D FFT，再对变换结果的每一列做1D FFT，两次变换顺序不影响最终结果。
你示例里的初始数据分布是MPI并行最常用的按行块划分：3个进程各持有矩阵的1整行，这种分布下第一阶段的行方向1D FFT完全不需要跨进程通信——每个进程本地存储的行数据是完整的，直接调用本地FFTW计算核就能算完。
第一阶段计算完成后必须做转置的核心原因非常直接：

此时所有列方向的元素是分散在全部进程上的，没有任何一个进程持有完整的一列数据，根本无法独立完成列方向的1D FFT计算。

全局矩阵转置操作本质是做一次进程间的全量数据交换（也就是你例子里列的P0到P2之间互相发数据的Alltoall通信），转置完成后，原矩阵的列会变成新矩阵的行，数据仍然保持按行块划分的分布，此时每个进程手里就持有了若干段完整的原矩阵列数据，可以无通信完成第二阶段的列方向1D FFT。
至于分块合并的逻辑：如果需要最终输出和输入保持相同的按行块分布，等列方向FFT计算完成后，需要再做一次和之前完全对称的全局转置，把傅里叶空间的数据从转置排布换回原矩阵的按行排布，所有进程持有的本地块按进程号拼接，就是完整的二维FFT结果。
这两次全局Alltoall转置，就是并行FFT最主要的通信开销来源——你示例里列的6条跨进程数据传输，就是3进程下第一次转置的全量通信量，如果走默认流程，最后转置还原排布还要再来一轮等量通信，总通信量直接翻倍。矩阵规模越大、进程数越多，通信占比越高，极端情况下通信耗时能占到总耗时的70%以上。

FFTW_MPI_TRANSPOSED_OUT/FFTW_MPI_TRANSPOSED_IN的底层省通信逻辑 #

这两个标志没有使用什么“傅里叶空间特殊转置算法”的黑科技，核心逻辑是砍掉了非必要的“数据排布还原”步骤，从接口约定上避免冗余通信：

• 默认不开启这两个标志时，FFTW的执行流程是：本地行FFT → 第一次全局转置（通信）→ 本地列FFT → 第二次全局转置（通信，把结果换回原输入的按行分布）→ 返回结果，整个流程做了两次全量跨进程数据交换。
• 开启FFTW_MPI_TRANSPOSED_OUT标志时，FFTW会直接跳过最后那次“把结果转回到原分布”的步骤：列方向FFT计算完成后，直接把转置排布下的傅里叶结果返回给调用方——也就是输出数据是按转置矩阵的行块划分（等价于原矩阵按列块划分），这一下就省掉了一整次全局Alltoall通信。
• FFTW_MPI_TRANSPOSED_IN标志是为流水线计算设计的：当你传入FFTW的输入本身就是转置排布的数据（比如上一步用FFTW_MPI_TRANSPOSED_OUT输出的傅里叶结果、或者做逆变换时的转置排布输入），这个标志会告诉FFTW不需要在计算前先把输入转回到原按行分布，直接在当前数据排布上启动计算，连第一次全局转置的通信都能省掉。

要注意的是，这两个标志不会减少任何FFT计算量，省掉的完全是为了“维持输入输出排布和原矩阵一致”而做的冗余转置通信。绝大多数使用FFT的科学计算场景（比如谱方法求解偏微分方程、大尺寸卷积、相关计算），后续逻辑根本不要求傅里叶系数严格按原矩阵的行块分布存储，只要能正确对应到频率索引即可，这种场景下用这两个标志能直接砍掉一半甚至全部的转置通信开销，收益非常明显。

内容的提问来源于stack exchange，提问作者Yes