2D FFT中的3D FFT分解

Question

基本上我使用FFT解決3D中的擴散方程，並行化的一種方法是在2D FFT中分解3D FFT。

如在本文中所描述：https://cmb.ornl.gov/members/z8g/csproject-report.pdf

分解一個三維FFT將通過執行方式：

2D FFT在xy方向的 全球轉置 1D FFT在z方向上的

基本上，我的問題是我不知道如何做這個全局轉置（因爲我認爲它是轉置一個3d數組我想）。任何人都有過這個問題？非常感謝。

Answer 1

想象一下帶有nx*ny*nz元素的3d立方體。這些元素的3D FFT在數學上是1-d FFT的3個階段，一個沿每個軸：

1. 待辦事項NY * NZ沿X軸變換，每個變換處理nx個元素
2. NX * NZ沿轉換Y軸
3. NX * NY沿Z軸轉換

更一般地，N維FFT（N> 1）由沿該軸許多（N-1）維的FFT。

如果信號是真實的，並且您有一個可以返回半頻譜的FFT，那麼第1階段的費用大約是一半（實際的FFT更便宜），其餘階段需要複雜，但它們只需要有大約一半的變換。所以成本大約是一半。

如果您的1d FFT可以讀取輸入元素並將輸出打包到連續的緩衝區中，那麼您最終會在每個階段進行轉置。

這就是kissfft執行多維FFT的方式。

P.S.當我需要獲得更高維度的精神圖片時，我想到： 帶有數字矩陣的紙張（2d），編號文件夾（3d），編號文件櫃（4d），編號房間（5d） ），在編號建築物（6D），等等......所以我們能想象的「文件櫃」維

Answer 2

在論文中提到的「全球換位」不是數學運算，而是distributed memory machines之間的數據重排。

步驟1中一臺機器上計算的數據必須傳輸到所有其他機器，反之亦然，步驟爲。它與矩陣換位無關。