MLSSM算法實現(xiàn)網(wǎng)格離散復雜目標的優(yōu)化設計

徐莉　潘宏　孫洪艷

摘 要： 為改進三維大尺寸復雜物體電磁建模精確求解的效率，采用了自適應交叉算法（ACA）基礎上的多層簡易矩陣稀疏算法（MLSSM）改進的方式，通過算法的理論及實現(xiàn)過程分析在實驗驗證中表明：應用的改進ACA算法計算效率比矩量法逐點計算顯著提高；改進的MLSSM的內(nèi)存需求減少了一半左右，矩陣構造過程速度有了明顯提高；改進的MLSSM降低了計算復雜度，迭代求解過程速度有了明顯提高。從算法對比結(jié)果可以看出，改進的MLSSM在降低計算復雜度方面占據(jù)優(yōu)勢，在分析半空間上大目標復雜物體優(yōu)勢明顯。這一研究對復雜物體的電磁建模優(yōu)化具有一定的理論和應用意義。

關鍵詞： 電磁建模； 精確求解； 復雜物體； 多層簡易矩陣稀疏算法； 自適應交叉算法

中圖分類號： TN911.7?34 文獻標識碼： A 文章編號： 1004?373X（2016）07?0161?06

Abstract： To improve the efficiency of exactly solving the electromagnetic modeling of large?size three?dimensional complex object， the improved multilayer simple sparse matrix （MLSSM） algorithm based on adaptive crossover algorithm （ACA） is adop?ted. The experimental verification of theory analysis and realization process shows that： the computing efficiency of using improved ACA algorithm is significantly increased than that of moment method； the memory requirement is reduced by a half by means of the improved MLSSM， which can significantly improve the speed of matrix construction process； the computing complexity is reduced by means of the improved MLSSM， and the speed of iterative solution process is significantly improved. The comparison results show that the improved MLSSM algorithm has the advantages in the aspects of reducing the computing complexity and analyzing the large complex object in half space. The study has certain theoretical and applied significances for the optimization of the complex object electromagnetic modeling.

Keywords： electromagnetic modeling； exact solution； complex object； multilayer simple sparse matrix algorithm； adaptive crossover algorithm

0 引 言

隨著科技不斷的飛速發(fā)展，對三維電較大對象的電磁建模，同時還做數(shù)值分析方面的深層研究，借助于計算機軟件以及硬件功能都得到了很大的提升，這讓從前沒辦法對某些對象做研究分析，而在現(xiàn)在能夠得以實現(xiàn)[1?3]。在現(xiàn)實社會中對于很大尺寸對象的研究分析預期借助計算機的功能水平大大高于實際發(fā)展的水平，所以如何提升數(shù)值運算的能力，是學者研究電磁學的關鍵因素。在三維電大尺寸對象的理論分析里，一般經(jīng)常用到的方法有微分、高頻等方法[4?5]。比如有限元法屬于微分法，物理光學法、幾何繞射理論屬于高頻方法。采用有限元方法雖能形成不太密集的矩陣，但其對欲求的對象做體剖分[6?7]。在分析對象的電尺寸非常大時，網(wǎng)格在離散時產(chǎn)生的未知量數(shù)目很多且無法預知，所以造成的運算量非常大。在高頻條件下的假設，高頻方法在面向較為復雜的對象時沒辦法得到精確的數(shù)據(jù)，所以無法應用[8]。而采用矩量法能夠得到精確的數(shù)據(jù)，任意幾何形狀以及復雜的物體都能適用，也不用增加吸收邊界條件，在做網(wǎng)格離散的時候，只用在被分析對象的表面上實施就可以，這樣一來，該算法的未知數(shù)就大大減少。傳統(tǒng)的矩量法得到的是稠密矩陣，在進行運算時會花費較多的時間以及空間，而當代的計算機要實現(xiàn)大尺寸對象運算非常困難[9?10]。本文基于上述背景，改進多層簡易矩陣稀疏算法實現(xiàn)網(wǎng)格離散復雜目標的優(yōu)化設計，這一研究對于復雜物體的電磁建模的優(yōu)化有一定的理論和應用意義。

1 MLSSM算法改進設計

一開始的多層簡易矩陣稀疏方法（MLSSM）是以直接的方法做求解的。該方法基于稀疏阻抗矩陣，而如今已成為迭代求解的方法，能夠在低秩類方法上構建起來。另外，還可以把阻抗矩陣用另外幾個更稀疏的矩陣以乘積的方式表達，其實就是低秩方法的再壓縮。以常見的低秩類方法產(chǎn)生的阻抗矩陣里，層和層無邏輯上的關系，每一層都相互獨立，并且在壓縮以后矩陣的秩只可以在某種角度上減小以及對中間范圍的電尺寸對象特征的分析。多層簡易矩陣稀疏的任意一層阻抗矩陣都是環(huán)環(huán)相扣的，產(chǎn)生的是嵌套結(jié)構，所以只能再減小內(nèi)存的需要以及提升矩陣矢量乘的處理。

1.1 自適應交叉算法（ACA）

同時把其代到式（4）能求得指定的頻帶內(nèi)任何范圍的頻率點的未知向量解[x（k）]。在進行求解時僅作一次矩陣求逆運算，就能夠得到全部頻帶內(nèi)的頻率響應。該優(yōu)點就是ACA算法能夠使得運算效率提升。

1.2 應用ACA優(yōu)點改進多層簡易矩陣稀疏方法

依照樹形結(jié)構，可以把阻抗矩陣分成近場[ZN]和遠場[ZF，]和其他快速算法不一樣的是，多層簡易矩陣稀疏方法把阻抗矩陣分成3部分。在其中任意一層的全部非空組，其阻抗元素有近場、本層遠場以及父層遠場3部分。在這里以一個四層八叉樹形成的阻抗矩陣為例。四層樹形結(jié)構的最細層的阻抗矩陣分解見圖1。

圖1右邊第一個子圖是描述近場組作用產(chǎn)生的矩陣。第二個子圖是本層遠場組對應的阻抗矩陣。第三個子圖是父層遠場組相互作用產(chǎn)生的矩陣。對于強相互作用的矩陣無需任何操作，采用矩量法做填充。弱相互作用部分采用ACA算法，MLSSM通過低秩類方法做填充。通常情況下，MLSSM可形成下面的遞歸表達式：

式中：[ZL]是在第[L+1]層遠場部分阻抗矩陣的稀疏描述方式，其任意一層的阻抗矩陣都有其對應的本層以及父層遠場；[ULZL-1VHL]是父層遠場部分；[ZL]是本層遠場部分，表示的是幾個稀疏矩陣相乘。當創(chuàng)建一層數(shù)為[L]的樹形結(jié)構時，最細層[ZL]描述的是近場組的阻抗矩陣，而在最粗層是沒父層遠場，因此，MLSSM由第[L]層遞歸到第2層。此時的矩陣元素全部是在復數(shù)域范圍里，[UL]稱作行基矩陣，[VL]稱作列基矩陣，[UL，VL]都是以對角方式的酉矩陣。和傳統(tǒng)的MLSSM對照，經(jīng)改進后的MLSSM只用保存[UL]以及[12]的[ZL-1，]這樣就減少了冗余的數(shù)據(jù)。按照這個方式，可以構造出和前面阻抗矩陣類似的表達式。

1.3 算法改進設計詳細說明

按照改良的MLSSM本質(zhì)思路，它的阻抗矩陣的表達式和MLSSM不一樣，這里敘述其構造方法以及步驟。

耦合矩陣也涵蓋了對應的本層遠場和父層遠場。本層遠場可形成最細層的耦合矩陣，父層遠場是下一層要操作的，在經(jīng)處理后可形成嵌套形式。

改進的MLSSM構造的步驟（如圖2所示）有下面三步：

（1） 在樹形結(jié)構的底層，通過采用ACA算法，可把全部遠場的阻抗矩陣做填充處理，得到子塊的[Uij]以及[VHij，]其全部是低秩矩陣，近場的阻抗矩陣可采用矩量法求得。

（2） 把前面的[Uij]按照非空組做組合，同時進行SVD分解后乘以[VHij，]采用式（12）的方法最后得到最細層的行基、列基矩陣以及耦合矩陣。

（3） 耦合矩陣分為兩個組成部分，把本層遠場部分進行存儲，父層遠場部分做UV分解處理，最終得到如同第一個步驟的兩個低秩矩陣相乘的表達式，即是次細層每個非空組的矩陣，反復進行前面敘述的步驟，一直到最粗層終止。

2 算法改進的實驗驗證

2.1 ACA算法優(yōu)勢驗證

由上面敘述的最終數(shù)據(jù)結(jié)果可知如下結(jié)論：

（1） 泰勒級數(shù)展開和帕德逼近都在一定范圍內(nèi)的頻帶和矩量法解一致，而帕德逼近比泰勒展開近似頻帶更寬，和理論分析一樣，預期效果也基本一致。

（2） 采用ACA算法可以較好的逼近雙負媒質(zhì)的MOM逐點運算解。表1說明了ACA算法能更好的得到雙負媒質(zhì)的寬頻RCS頻率響應，其效率比矩量法逐點的方式進行運算提升了很多。

2.2 壓縮效果的對比驗證

要證明經(jīng)改進的MLSSM比傳統(tǒng)的MLSSM對ACA壓縮的效果更加明顯，本文給出了幾個數(shù)據(jù)進行驗證。這幾個數(shù)例在測試過程中，都在同一計算機設備配置下進行。最初，為保證實驗流程的準確，還對一個半徑為2.4 m的金屬球進行了測試，預設的平面波入射頻率是300 MHz，其波長[λ=1 m，]入射角[θi=0°，][?i=0°。]依據(jù)[0.1λ]的標準采取RWG基函數(shù)的方式將其表面做網(wǎng)格離散處理，之后未知量有23 952個。構建一個三層的樹形結(jié)構，設置[0.3λ]為其最細層的電尺寸。再進行阻抗矩陣填充，ACA的截斷公差是[1×10-3，]而MLSSM、改進的MLSSM的奇異值分解截斷參數(shù)都一樣，也是[1×10-3。]最后生成的方程組通過以GMRES方式進行迭代求解，設定收斂精度為[1×10-3。]此時，這兩種方式都各自計算金屬球的雙站RCS，同時把這種結(jié)構以及Mie級數(shù)做對比，能夠發(fā)現(xiàn)數(shù)據(jù)結(jié)果是吻合的，由此證明本文的運算結(jié)果是對的，如圖5所示。表2將MLSSM與改進的MLSSM需占據(jù)的內(nèi)存以及在進行迭代時耗費的時間做對照，能夠知曉改進的MLSSM所需空間減少了一半，并且矩陣的構造提高了效率。

接著，分析如圖6所示的自由空間導彈模型的散射特性。其電尺寸是[16λ，]平面波入射頻率[f]為800 MHz，其波長為[λ=0.375 m，]入射角[θi=0°，?i=0°，]依據(jù)[0.1λ]的標準采取RWG基函數(shù)的方式將其表面做網(wǎng)格離散處理，之后未知量有56 859個。再進行阻抗矩陣填充，ACA的截斷公差是[1×10-3，]而MLSSM、改進的MLSSM的奇異值分解截斷參數(shù)都一樣，也是[1×10-3。]構建一個四層的樹形結(jié)構對此模型做分組，最后生成的方程組通過以GMRES方式進行迭代求解，設定收斂精度為[1×10-3。]此時，這兩種方式都各自計算此模型雙站RCS，見圖7，發(fā)現(xiàn)數(shù)據(jù)結(jié)果是吻合的。表3將MLSSM與改進的MLSSM在需占據(jù)的內(nèi)存、構造時間以及在進行迭代時耗費的時間做對照，能夠知曉改進的MLSSM的運算降低了難度，并且在矩陣的構造以及迭代運算上都提高了效率。

如果需要計算的對象在有耗半空間的上方，因為并矢格林函數(shù)具有較為復雜的形式，其計算采用快速多極子難度較大；加上快速多極子受到分組的限制，通常情況下，它有以下三個環(huán)節(jié)，即聚合、轉(zhuǎn)移以及配置；如果分組過大，即便轉(zhuǎn)移過程可正常進行，但在一定程度上會降低聚合與配置過程的效率；如果分組過小，情況剛好相反，其轉(zhuǎn)移過程與計算相對會變得更加復雜，而聚合與配置過程則沒有多大影響。因此，分組大小要恰當，這樣快速多極子才發(fā)揮其最大的效率，通常最細層的電尺寸不能超過[0.2～0.4λ]這個范圍。經(jīng)過改進的MLSSM方法是基于ACA而建立的，屬于純代數(shù)方法，這點與ACA相同，并不只局限于格林函數(shù)的形式，它就是對矩陣的數(shù)學壓縮，沒有快速多極子聚合轉(zhuǎn)移配置的過程，所以也不受限于分組。由以上兩個優(yōu)點可知，經(jīng)過改進的MLSSM非常適用于對有耗半空間上目標的分析。

3 結(jié) 語

本文對矩量法中的快速迭代法進行了概括，著重對MLSSM的阻抗矩陣形式進行了分析，同時采取了一種新的方法作出了相應的改進，經(jīng)過改進的MLSSM是對低秩類方法的進一步壓縮，新的MLSSM計算相對要簡單很多，其嵌套結(jié)構使矩陣矢量乘操作速度加快，數(shù)值算例分析對其正確性、有效性以及實用性進行了驗證，與其他算法相比，它在很大程度上可以減少同一模型的計算量，而且還是代數(shù)類方法，就算沒有使用格林函數(shù)的形式，也可不受分組的限制，在分析環(huán)境較為復雜的電磁問題中比較適用。

參考文獻

[1] 王鼎，吳瑛.一種利用互耦矩陣稀疏性的陣列誤差有源校正改進算法[J].信號處理，2009（9）：1414?1420.

[2] 杜吉祥，余慶，翟傳敏.基于稀疏性約束非負矩陣分解的人臉年齡估計方法[J].山東大學學報（理學版），2010（7）：65?69.

[3] ZHANG Z C， HONG H S， WAI O W， et al. Parallel hydrodynamic finite element model with an N?Best refining partition scheme [J]. Chinese journal of oceanology and limnology， 2010， 28（6）： 1340?1349.

[4] 崔樹標，張云，周華民，等.邊界元矩陣稀疏化算法及其應用[J].上海交通大學學報，2008（10）：1618?1621.

[5] 彭志威，王波，保錚，等.矩陣稀疏化中的最優(yōu)子波濾波器組設計[J].西安電子科技大學學報，1999（1）：35?40.

[6] ZHONG Weitao， SHAO Zhijiang， ZHANG Yuyue， et al. Applying analytical derivative and sparse matrix techniques to large?scale process optimization problems [J]. Chinese journal of chemical engineering， 2000， 8（3）： 212?217.

[7] 程耿東.線性規(guī)劃在結(jié)構優(yōu)化設計中的一個應用及其稀疏算法[J].大連工學院學報，1979（1）：22?31.

[8] REN Jianmin， ZHANG Yimen. A sparse matrix technique for simulating semiconductor devices and its algorithms [J]. Journal of electronics （China）， 1990， 7（1）： 77?82.

[9] ZHENG Xiaolang， YANG Yiwei. A sparse matrix model?based optical proximity correction algorithm with model?based mapping between segments and control sites [J]. Journal of Zhejiang University science C， 2011， 12（7）： 436?442.

[10] FAN P， CAO Z. A matrix algorithm for computing the free space distance of TCM signal sequences [J]. Journal of electronics （China）， 1997， 14（4）： 328?335.