多層快速多極子算法(MLFMA)是快速多極子算法(FMM)在多層結構中的一種推廣，與快速多極子算法不同的是，多層快速多極子算法除了分組還有一個分層的概念。它通過逐層聚合、轉移、解聚，從而完成相應的矩矢乘運算。多層快速多極子算法可以將計算複雜度和存儲量都降低到 O（N log N），將更加適用於解決電大尺寸目標的電磁輻射與散射問題。
基本介紹
- 中文名：多層快速多極子算法
- 外文名：Multi Level FastMultipole Method
- 簡稱：MLFMM
- 提出者：J．M．Song，C．C．Lu等
- 套用：電大尺寸目標的電磁輻射問題等
- 複雜度：O(NlogN)
發展,基本原理,算法實現,多層快速多極子算法的結構特點,多層快速多極子算法中的若干關鍵技術,層間的遞推,轉移項的對角化和快速計算,層快速多極子算法中的若干共性問題,存儲量,計算量,
發展
自上世紀60年代R．F．Harrington將矩量法MOM(Method OfMoment)用於電磁散射分析以來，計算電磁學得到了快速的發展。MOM以及基於MOM的各種快速算法因為它們相對於近似算法的精確性和它們相對於解析算法的通用性在計算電磁學的發展中占據了極其重要的地位。但是由於其巨大的存儲量O(
)和計算量O( )使得能夠解決的問題一直局限於電小尺寸，而工程中對電大尺寸目標散射的分析一直以來只能藉助於高頻方法。
1989年，耶魯大學(YaleUniversity)的V．Rokhlin教授將快速多極子方法FMM(Fast Multipole Method)使用於靜電場問題中的泊松方程的求解後才得到了改觀。FMM的計算和存儲複雜度都是O(
)。
90年代中期，J．M．Song，C．C．Lu等將FMM套用於分析三維目標的散射問題，並提出了用於分析二維和三維目標的散射問題的多層快速多極子方法MLFMM(Multi Level FastMultipole Method)。
此後FMM和MLFMM得到了快速的發展。其中，以美國伊利諾伊大學的W．C．Chew教授矛NDemaco公司合作開發出基於快速多極子方法和多層快速多極子方法的FISC軟體，標誌著快速多極子方法和多層快速多極子方法在計算電磁學領域進入了成熟套用階段。使得精確方法逐漸能夠解決以前只能使用高頻近似方法解決的問題。
基本原理
對於二維情況，多層快速多極子算法將求解區域用一正方形包圍，然後再細分為4個子正方形，該層記為第一層。將每個子正方形再細分為4個更小的子正方形，則得到第二層，此時共有
個正方形。依次類推得到更高層。對於三維情況，則用一正方體包圍記為0層，經過一次細分後得到8個子正方體記為第1層。依次類推細分下去，直到子正方體的邊長為0.2λ左右。由此可以確定多層快速多極子方法在求解一個給定電尺寸的目標散射時所需的層數。顯然，對於二維，三維情況，第i 層正方形或正方體的數目分別為
或
。這種樹形分層級結構如圖1所示。
圖1 二維多層快速多極子方法的分層結構示意圖
圖2
和快速多極子方法一樣，多層快速多極子方法的矩陣矢量乘同樣可以分解成聚合、轉移、配置三個部分。不過多層快速多極子方法中和快速多極子方法中的聚合、轉移、配置有所不同，在快速多極子方法中聚合、轉移、配置只發生在一層，即在最細層某個組除了近場組，其它所有的組都屬於遠場組需要轉移過來。而在多層快速多極子方法中，首先在最細層將各個非空組內的散射體的貢獻聚合到該組的中心，然後進行該層內部的轉移操作，這種
圖3
轉移操作只在本層滿足本層是遠場而父層是近場的組之間發生作用。具體如圖2所示，圖2中的圖a表示一個二維目標的樹形結構分組示意圖，圖2中的圖b中黑色表示觀察點所在的組，斜線表示快速多極子方法作用的區。圖3表示在多層快速多極子方法中的作用方式，其中遠場分分為斜線和網狀區域，其中斜線符合多層快速多極子的在本層屬於遠場組而在父層是近場組的條件，因此在最細層發生轉移的作用。完成同層之間內部的轉移操作之後，將各個組中心的聚合因子通過插值聚合到高一層中本組的父層組。接著完成父層組之間的滿足轉移條件的遠場組之間的轉移。如圖3中的網狀區域。如此遞推至第二層。到此，聚合、轉移過程算是完成。然後從第二層開始各個非空組將通過轉移得到的平面波數通過反向插值技術，得到子層組的內向波表達式。這種操作一直進行下去直至配置到最細層組為止。從而完成整個多層快速多極子方法逐層聚合、逐層轉移、逐層配置的過程。
算法實現
多層快速多極子算法的實現是首先將目標劃分為多層的格線，每一個格線稱為一個組，在各層的格線的組中心採用快速多極子方法，並且在層與層之間採用插值技術遞推。從而進一步降低計算和存儲複雜度。其具體的實現公式可以用下面的表示：
其中，U、T、V分別是第n層中的配置、轉移、聚合矩陣。U，V在不同層之間是可以通過插值來遞推的，這也就保證了只需要在最細層中計算一次聚合配置量，而其他層中的聚合配置量通過插值來得到。
多層快速多極子算法的結構特點
多層快速多極子算法是基於樹形結構的計算，其特點是逐層聚合、逐層轉移、逐層配置、嵌套遞推。
它的基本步驟是：聚合、轉移、配置過程。即先將最細層組內的子散射體的貢獻聚合到該組中心，然後進行該層內部的遠親組之間的轉移(將源區組的組中心的外向波表達轉移至場區組的組中心的內向波表達)，完成轉移後再將各個組中心的外向波表達向上聚合至高一層中對應父組的組中心位置的外向波表達，接著完成該層中的遠親組的轉移過程，如此遞推，直至聚合至多極子樹的第2層。此時，由於該層中所有的非附近組就是其遠親組，從而通過計算第二層中的轉移就可以求得所有的非附近組的內向波，到此，這個上聚過程完成。然後進行向下配置的過程，就是通過每一層中高層的組中心的內向波表達和伴隨內插技術得到低層的組中心的內向波表達，直至配置到最細層為止，從而完成整個多極子的過程。
基於以上的多層級的算法結構，多層快速多極子算法由上行和下行兩個部分組成。上行部分主要包含從最細層的多極展開，子層到父層的多極聚合，同層遠親組之間的多極轉移。在完成向第二層的多極聚合和第二層之間的多極轉移之後，程式轉入下行過程，主要包含從父層到子層的多極配置和在最細層的部分場展開的過程。
多層快速多極子算法中的若干關鍵技術
層間的遞推
由上面的多層快速多極子算法的思路可以看出，在每一層中都需要知道接收和發射方向圖，這是通過層間的內插和伴隨內插來完成的。
由下面的公式可以表示層與層之間的聚合配置量的遞推關係：
由上面的兩式就可以導出接收發射方向圖的層間遞推關係，從而完成多層快速多極子算法中的多極聚合和多極配置的過程。
轉移項的對角化和快速計算
計算轉移量也是相當耗時間的。所以採用了FLEA算法，當插值點數取為2
時可以將計算複雜度降低到O(
)但是存儲量仍然較大，為了兼顧存儲複雜度和計算複雜度的要求，採用了MLIT技術，該技術的思想是首先通過FLEA算法在每一層上計算出若干個插值點(這些插值點是分布在不同的r和不同的r與K的夾角上的)的轉移因子的值，在完成矩陣矢量相乘中需要使用轉移園子時，通過在距離和夾角上的二維插值得到當前需要的轉移因子的值，這樣既可以維持原來計算量的量級，同時可以大大地降低存儲量的需求。
層快速多極子算法中的若干共性問題
存儲量
作為基於積分方程方法的快速算法，雖然一定程度上降低了對存儲量的要求，但是存儲量是限制並行多層快速多極子算法求解電大問題的一個重要的瓶頸，其中用於附近組元素的存儲、接收發射方向圖的存儲和基函式的聚合配置因子是並行多層快速多極子算法中記憶體需求最大的幾個部分。
計算量
另一個制約並行多層快速多極子算法求解電大尺寸問題能力的是計算的效率，由於基於嚴格的積分方程方法，計算量還是相當大的。其中疊代求解線性方程組的時間占據了整個程式花費時間的絕大多數。在疊代的過程中又是矩矢相乘的時間占據了總計算時間的大部分，尤其是在計算遠區的矩陣元素和矢量相乘時的轉移因子的計算量在總計算量中占了相當重要的部分。
