自適應(yīng)交叉近似算法的核外計(jì)算方法

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

(1.空軍西安飛行學(xué)院,陜西西安 710300;2.西安電子科技大學(xué)天線與微波技術(shù)重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071;3.空軍工程大學(xué)信息與導(dǎo)航學(xué)院,陜西西安 710077)

自適應(yīng)交叉近似算法的核外計(jì)算方法

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

(1.空軍西安飛行學(xué)院,陜西西安 710300;2.西安電子科技大學(xué)天線與微波技術(shù)重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071;3.空軍工程大學(xué)信息與導(dǎo)航學(xué)院,陜西西安 710077)

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

自適應(yīng)交叉近似算法;矩量法;核外求解;雷達(dá)散射截面

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

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

1 自適應(yīng)交叉近似算法

自適應(yīng)交叉近似算法是利用遠(yuǎn)場(chǎng)組所形成的阻抗矩陣的低秩特性,對(duì)其進(jìn)行分解,形成一對(duì)小型的滿秩矩陣塊來(lái)代表矩量法中的遠(yuǎn)場(chǎng)互作用矩陣,從而有效地對(duì)遠(yuǎn)場(chǎng)子矩陣塊進(jìn)行壓縮.Zm×n代表矩量法中兩個(gè)遠(yuǎn)場(chǎng)組的互阻抗[9],自適應(yīng)交叉近似算法即采用兩個(gè)滿秩矩陣乘積的形式構(gòu)造來(lái)近似表達(dá)Zm×n,即

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

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

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

初始化部分:

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

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

(3)在第1行搜索最大值確定第1個(gè)列標(biāo)號(hào)J1,使得

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

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

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

(8)搜索第1列最大值確定第2個(gè)行標(biāo)號(hào)I2:

第k次迭代:

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

(2)搜索第Ik行中最大值確定第k個(gè)列的標(biāo)號(hào)Jk,使得

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

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

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

(8)尋找下一個(gè)行標(biāo)號(hào)Ik+1:

2 核外存取與求解

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

2.1 核外存取

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

2.2 核外求解

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

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

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

如果Aij經(jīng)過(guò)了壓縮,是采用兩個(gè)滿秩矩陣近似的,那么式(4)可轉(zhuǎn)化為

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

zi=AHri的計(jì)算與上述過(guò)程類(lèi)似,這里不再贅述.由于自適應(yīng)交叉近似算法本身對(duì)阻抗矩陣進(jìn)行了分組,所以核外求解時(shí)的分塊計(jì)算并沒(méi)有增加額外的計(jì)算量.

3 計(jì)算實(shí)例

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

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

圖1 波長(zhǎng)1 m球體x Oz面上歸一化雷達(dá)散射截面

表1 球體雷達(dá)散射截面求解所需內(nèi)存和迭代時(shí)間

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

圖2 波長(zhǎng)0.25 m球體x Oz面上歸一化雷達(dá)散射截面

圖3 金屬導(dǎo)彈x Oz面上雷達(dá)散射截面

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

4 結(jié) 論

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

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

[2]滿明遠(yuǎn),雷振亞,謝擁軍,等.電大目標(biāo)散射問(wèn)題的預(yù)修正多層快速多極子分析[J].西安電子科技大學(xué)學(xué)報(bào),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]馬驥,龔書(shū)喜,王興,等.一種快速計(jì)算目標(biāo)寬帶雷達(dá)截面的電磁算法[J].西安電子科技大學(xué)學(xué)報(bào),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]徐曉飛,曹祥玉,高軍,等.基于矩量法的電大目標(biāo)RCS核外并行計(jì)算[J].電子與信息學(xué)報(bào),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">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2014-01-12

國(guó)家自然科學(xué)基金資助項(xiàng)目(60671001,61072018,61271100);陜西省自然科學(xué)基金資助項(xiàng)目(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