吳君輝,梁昌洪,袁浩波,曹祥玉

(1.空軍西安飛行學院,陜西西安 710300;2.西安電子科技大學天線與微波技術重點實驗室,陜西西安 710071;3.空軍工程大學信息與導航學院,陜西西安 710077)

自適應交叉近似算法的核外計算方法

吳君輝1,梁昌洪2,袁浩波2,曹祥玉3

(1.空軍西安飛行學院,陜西西安 710300;2.西安電子科技大學天線與微波技術重點實驗室,陜西西安 710071;3.空軍工程大學信息與導航學院,陜西西安 710077)

為解決矩量法在計算電大目標電磁特性時受計算機物理內存限制的問題,設計了一種核外自適應交叉近似算法.使用自適應交叉近似算法有效地壓縮了阻抗矩陣,降低了所需存儲空間和計算量;并結合核外技術,進一步節(jié)省了內存空間,提升了單臺計算機的計算能力.通過算例檢驗了文中方法的準確性和有效性,結果表明:該方法有效地降低了求解電大目標雷達散射截面所需的內存和計算量,并且自適應交叉近似算法及核外計算不損失矩量法的計算精度.

自適應交叉近似算法;矩量法;核外求解;雷達散射截面

矩量法是一種可以精確分析目標雷達散射截面的數(shù)值計算積分方程方法.但隨著目標電尺寸的增大,所需存儲空間和計算復雜度也急劇增加,以至超出了單機的內存容量,無法在單臺計算機上求解.為降低矩量法所需內存和計算量,出現(xiàn)了多種快速算法,例如快速多極子[1]、多層快速多極子[2]、自適應積分方法[3]、快速傅里葉變換法[4]、自適應交叉近似算法[5]等.快速多極子及多層快速多極子可以將存儲量由O(N2)降到O(N1.5),計算量由直接解的O(N3)降到O(N log N),但它依賴于加法定理對格林函數(shù)的展開,因此,其公式的推導、執(zhí)行及運算往往需要預先已知格林函數(shù).自適應積分方法、快速傅里葉變換法可以在傅里葉空間完成矩量法求解中的矩陣矢量乘,從而避免將阻抗矩陣元素直接存儲,所需內存可降為O(N log N),計算復雜度降低為O(k N log N),但它更適用于體積分方程,表面積分方程效果較差.

自適應交叉近似算法是利用線性相關性來對低秩矩陣進行壓縮的,可將存儲量和計算量降為O(N log N).它由Bebendorf在2000年首先提出[5],并迅速被運用到多種數(shù)值算法中.2005年Zhao等將自適應交叉近似算法引入矩量法,用于分析電磁輻射與散射[6].2011年Tamayo等更將自適應交叉近似算法拓展到多層自適應交叉近似算法的概念[7].自適應交叉近似算法的優(yōu)點在于它是一種純數(shù)學方法,不依賴于格林函數(shù)展開及積分方程、基函數(shù),更容易應用到矩量法計算中.雖然自適應交叉近似算法可以極大地減小矩量法所需的內存空間,但計算機的內存資源畢竟有限且價格相對昂貴.結合核外技術,將經過自適應交叉近似算法壓縮過的矩陣存儲到擁有更大空間的硬盤上[8],求解時分塊提取,逐塊求解,可以進一步提升單臺計算機的求解能力.

1 自適應交叉近似算法

自適應交叉近似算法是利用遠場組所形成的阻抗矩陣的低秩特性,對其進行分解,形成一對小型的滿秩矩陣塊來代表矩量法中的遠場互作用矩陣,從而有效地對遠場子矩陣塊進行壓縮.Zm×n代表矩量法中兩個遠場組的互阻抗[9],自適應交叉近似算法即采用兩個滿秩矩陣乘積的形式構造來近似表達Zm×n,即

其中,r為矩陣Zm×n的有效秩,Um×r和Vr×n為兩個滿秩矩陣.秩r的選取根據下式得到[10]:

當Zm×n用Um×r和Vr×n兩個矩陣表示時,存儲量由m×n變?yōu)閞×(m+n).若r×(m+n)＜m×n(通常r?min(m,n)),則自適應交叉近似算法只需保存Um×r和Vr×n這兩個規(guī)模較小的矩陣,從而實現(xiàn)了矩陣的壓縮.

自適應交叉近似算法可以按照下面的流程實現(xiàn)[5,11]:

初始化部分:

(1)初始化第1個行索引:I1=1,初始化=0;

(2)初始化誤差矩陣的第1行:R(I1,:)=Z(I1,:);

(3)在第1行搜索最大值確定第1個列標號J1,使得

(4)V矩陣第1行表示為v1=R(I1,:)R(I1,J1);

(5)初始化誤差矩陣的第1列:R(:,J1)=Z(:,J1);

(6)則U矩陣每一列為u1=R(:,J1);

(8)搜索第1列最大值確定第2個行標號I2:

第k次迭代:

(1)更新誤差矩陣的第Ik行:

(2)搜索第Ik行中最大值確定第k個列的標號Jk,使得

(3)V矩陣第k行:vk=R(Ik,:)R(Ik,Jk);

(4)更新誤差矩陣第Jk列:

(5)U矩陣每k列:uk=R(:,Jk);

(8)尋找下一個行標號Ik+1:

2 核外存取與求解

由于自適應交叉近似算法的思想是從分組入手,將阻抗矩陣分解成一系列子矩陣塊,并對其進行壓縮,所以算法本身需要對阻抗矩陣進行分組.采用核外技術進行求解,只需將阻抗矩陣按分組壓縮后存儲在硬盤中,進行核外計算時每次將計算所需的分組子矩陣讀入內存逐塊求解,不增加計算復雜度.

2.1 核外存取

矩量法形成的阻抗矩陣是一個稠密陣,矩陣規(guī)模和每個元素的位置都是固定的,核外存儲時只需順序存儲,在讀取時可根據元素在矩陣中的位置推算它在核外文件中的起始地址.與矩量法不同,自適應交叉近似算法得到的阻抗矩陣的大小是不固定的,它將阻抗矩陣分為多個子矩陣,逐塊計算,并根據遠場互作用阻抗的低秩特性進行矩陣壓縮.相互距離不同,各子矩陣的壓縮程度不同,距離越遠,壓縮效果越好,而兩個相鄰區(qū)域的阻抗元素甚至不能壓縮.這導致無法確定某一分組矩陣在核外文件中的起始地址,因此,需要建立一個數(shù)組記錄每一個子矩陣的形態(tài)、起始地址以及是否進行了壓縮.在內存分配一個三維數(shù)組ACAREC[N][N][6],其中N為分組數(shù),第三維的6個元素分別記錄該子矩陣在文件中的起始地址、長度、是否進行壓縮以及壓縮后的兩個滿秩矩陣的行列數(shù)m、r、n.阻抗矩陣填充完畢后,數(shù)組ACAREC記錄了所有分組的存儲信息,在計算時就可以通過數(shù)組中的信息逐個讀取阻抗子矩陣[8].

2.2 核外求解

由于自適應交叉近似算法將阻抗矩陣分組計算,子矩陣在壓縮后,由兩個滿秩矩陣組成,已經不再是原始阻抗矩陣的形式,因此,矩矢乘的計算必須采用逐塊分步計算,將分步結果相加組成最終矢量的方式.核外求解并不改變這一過程,只是多了從硬盤讀取數(shù)據的過程.

這里利用共軛梯度殘差法(CGNR)進行核外求解.假設自適應交叉近似算法在矩陣填充時將阻抗矩陣A分為16個分組分別計算,那么在核外存儲也是按照分組將矩陣分為16個子矩陣.CGNR在迭代過程中,需要阻抗矩陣參與計算的步驟是wi=Api和zi=AHri,即阻抗矩陣與矢量相乘和阻抗矩陣的共軛轉置與矢量相乘.以wi=Api的計算為例,阻抗矩陣A在核外是按照分組存儲的,因此,將相乘的矢量也相應分組,如式(3)將矩陣分為16個子矩陣,每個子矩陣用Aij表示,已知相乘矢量相應分為4個子矢量列,用pj表示,

則wi可通過處在第i行的子矩陣Aij分別與相應的子矢量列pj相乘后全部相加得到,如

如果Aij經過了壓縮,是采用兩個滿秩矩陣近似的,那么式(4)可轉化為

由于矩陣采用核外存儲,每計算一個子矩陣的矩矢乘都需要讀取一次核外文件,根據數(shù)組ACAREC記錄的信息,提取出相應子矩陣,并將計算結果記錄在內存.式(5)需要讀取4次核外數(shù)據,整個阻抗矩陣的計算需讀取16次,也就是分組個數(shù).

zi=AHri的計算與上述過程類似,這里不再贅述.由于自適應交叉近似算法本身對阻抗矩陣進行了分組,所以核外求解時的分塊計算并沒有增加額外的計算量.

3 計算實例

計算如圖1所示金屬圓球的雷達散射截面(RCS),并與Mie級數(shù)對比以驗證算法的準確性.球半徑為1 m,剖分尺寸為0.06 m,剖分為2 724個三角形面片,未知數(shù)有4 086個.激勵平面波的波長為1 m,由-z方向入射,沿x方向極化.如圖1所示,核外自適應交叉近似算法、自適應交叉近似算法與矩量法相比,它們計算雷達散射截面(RCS)的結果一致,與Mie級數(shù)結果吻合良好,說明自適應交叉近似算法不損失矩量法計算精度,且核外計算不影響自適應交叉近似算法的計算結果.

表1體現(xiàn)了當物體剖分變密,未知量數(shù)目增大時運算過程所占內存和迭代求解時間的變化趨勢.可以看出,矩量法的存儲量增加趨勢為O(N2),而交叉近似算法對內存的要求為O(N log N),自適應交叉近似算法對矩陣矢量乘的加速也使其迭代時間小于矩量法的計算時間.當矩陣規(guī)模增大時,自適應交叉近似算法優(yōu)勢顯現(xiàn).而核外自適應交叉近似算法由于每次計算只需存儲一個子矩陣的數(shù)據,內存需求非常小.盡管核外讀取數(shù)據需耗費一定時間,但結合自適應交叉近似算法,核外算法的計算效率仍優(yōu)于矩量法.

圖1 波長1 m球體x Oz面上歸一化雷達散射截面

表1 球體雷達散射截面求解所需內存和迭代時間

為進一步驗證算法求解電大問題的有效性和穩(wěn)定性,增加球體的電尺寸,球半徑為1 m,剖分為32 736個三角形面片,未知數(shù)49 104個.激勵平面波的波長為0.25 m,由-z方向入射,沿x方向極化.計算此金屬球矩量法理論需內存18.4 GB,采用自適應交叉近似算法及核外自適應交叉近似算法可以正常計算.如圖2所示,核外自適應交叉近似算法、自適應交叉近似算法與Mie級數(shù)結果吻合良好,說明核外自適應交叉近似算法求解電大問題結果依然精確.

圖2 波長0.25 m球體x Oz面上歸一化雷達散射截面

圖3 金屬導彈x Oz面上雷達散射截面

接著驗證算法計算復雜形狀目標的有效性,計算一金屬導彈模型如圖3所示,電尺寸約14λ×12λ×3λ,剖分為30 780個三角形面片,未知數(shù)為46 170,入射波同上例.矩量法理論需內存16.26 GB,超過普通計算機物理內存,采用快速多極子算法需占用內存1.83 GB,而采用核外自適應交叉近似算法只需占用155 MB即可計算得到導彈的RCS,結果如圖3所示.但是在計算時間上核外自適應交叉近似算法花費711 min,比快速多極子多耗時約80 min.這在一定程度上因為采用核外計算在硬盤存取數(shù)據上需花費一定時間,如何高效地存取數(shù)據是下一步研究的重點.

4 結 論

矩量法計算電大物體的雷達散射截面存在占用內存空間及計算量巨大的問題,自適應交叉近似算法可以有效地壓縮阻抗矩陣,加速矩陣填充和矩陣向量乘,該運算可以提升矩量法的計算效率;采用核外技術可以進一步節(jié)省內存空間,擴大單臺計算機的計算能力.計算結果表明,此方法有效地降低了矩量法所需內存和計算量,并且自適應交叉近似算法及核外計算不影響矩量法的計算精度.

[1]Rokhlin V.Rapid Solution of Integral Equations of Classic Potential Theory[J].Journal of Computer Physics,1985,60 (2):187-207.

[2]滿明遠,雷振亞,謝擁軍,等.電大目標散射問題的預修正多層快速多極子分析[J].西安電子科技大學學報,2012, 39(2):133-136.

Man Mingyuan,Lei Zhenya,Xie Yongjun,et al.Analysis of the Electrical Large Scattering Problem Using the Precorrected Multilevel Fast Multipole Algorithm[J].Journal of Xidian University,2012,39(2):133-136.

[3]馬驥,龔書喜,王興,等.一種快速計算目標寬帶雷達截面的電磁算法[J].西安電子科技大學學報,2012,39(4):98-101.

Ma Ji,Gong Shuxi,Wang Xing,et al.Fast Computation of the Wide-band Radar Cross Section of Arbitrary Objects[J]. Journal of Xidian University,2012,39(4):98-101.

[4]Zhao Y,Zhang M,Chen H.The EM Scattering of Electrically Large Dielectric Rough Sea Surface at 240 GHz[J].IEEE Transactions on Antennas and Propagation,2012,60(12):5890-5899.

[5]Bebendorf M.Approximation of Boundary Element Matrices[J].Numerische Mathematik,2000,86(4):565-589.

[6]Zhao K,Vouvakis M N,Lee J F.The Adaptive Cross Approximation Algorithm for Accelerated Method of Moments Computations of EMC Problems[J].IEEE Transactions on Electromagnetic Compatibility,2005,47(4):763-773.

[7]Tamayo J M,Heldring A,Rius J M.Multilevel Adaptive Cross Approximation(MLACA)[J].IEEE Transactions on Antennas and Propagation,2011,59(12):4600-4608.

[8]徐曉飛,曹祥玉,高軍,等.基于矩量法的電大目標RCS核外并行計算[J].電子與信息學報,2011,33(3):758-762.

Xu Xiaofei,Cao Xiangyu,Gao Jun,et al.Parallel Out-of-core Calculation of Electrically Large Objects’RCS Based on MOM[J].Journal of Electronics&Information Teohnology,2011,33(3):758-762.

[9]Yan Ying,Zhang Yu,Zhao Xunwang,et al.Time-domain Method of Moments Accelerated by Adaptive Cross Approximation Algorithm[C]//IEEE Antennas and Propagation Society International Symposition.Piscataway:IEEE, 2012:6348636.

[10]Guo Han,Hu Jun,Shao Hanru,et al.Accelerating Calderón Multiplicative Preconditioner with Multi-grade Adaptive Cross Approximation Algorithm[C]//IEEE Antennas and Propagation Society International Symposition.Piscataway: IEEE,2011:201-204.

[11]Shaeffer J.Direct Solve of Electrically Large Integral Equations for Problem Sizes to 1 M Unknowns[J].IEEE Transactions on Antennas and Propagation,2008,56(8):2306-2313.

(編輯:李恩科)

Out-of-core computing method of the adaptive cross approximation algorithm

WU Junhui1,LIANG Changhong2,YUAN Haobo2,CAO Xiangyu3
(1.PLA Air Force Xi’an Flight Academy,Xi’an 710300,China;2.Science and Technology on Antenna and Microwave Lab.,Xidian Univ.,Xi’an 710071,China;3.School of Information and Navigation, Air Force Engineering University,Xi’an 710077,China)

In order to solve computer memory limitation when computing the scattering characteristic of an electrically large target,the out-of-core adaptive cross approximation algorithm is designed.The adaptive cross approximation algorithm is used to compress the impedance matrix and reduce the computation complexity and storage effectively.By the use of the out-of-core technology,the memory space is reduced further and the calculating power of a single computer is raised by this method.The validity and effectiveness of the method are testified by numerical examples.lt is proved that the memory and computing time is reduced by this method when solving the radar cross section of a large target without losing the accuracy of the moment method.

adaptive cross approximation algorithm;method of moment;out-of-core solver;radar cross section

TN011

A

1001-2400(2014)05-0161-05

2013-05-06< class="emphasis_bold">網絡出版時間:

時間:2014-01-12

國家自然科學基金資助項目(60671001,61072018,61271100);陜西省自然科學基金資助項目(2012JM8003)

吳君輝(1985-),女,博士,E-mail:wjhyouxiang@163.com.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.027.html

10.3969/j.issn.1001-2400.2014.05.027