自适应交叉近似算法的核外计算方法

吴君辉,梁昌洪,袁浩波,曹祥玉

(1.空军西安飞行学院,陕西西安 710300;2.西安电子科技大学天线与微波技术重点实验室,陕西西安 710071;3.空军工程大学信息与导航学院,陕西西安 710077)

自适应交叉近似算法的核外计算方法

吴君辉1,梁昌洪2,袁浩波2,曹祥玉3

(1.空军西安飞行学院,陕西西安 710300;2.西安电子科技大学天线与微波技术重点实验室,陕西西安 710071;3.空军工程大学信息与导航学院,陕西西安 710077)

为解决矩量法在计算电大目标电磁特性时受计算机物理内存限制的问题,设计了一种核外自适应交叉近似算法.使用自适应交叉近似算法有效地压缩了阻抗矩阵,降低了所需存储空间和计算量;并结合核外技术,进一步节省了内存空间,提升了单台计算机的计算能力.通过算例检验了文中方法的准确性和有效性,结果表明:该方法有效地降低了求解电大目标雷达散射截面所需的内存和计算量,并且自适应交叉近似算法及核外计算不损失矩量法的计算精度.

自适应交叉近似算法;矩量法;核外求解;雷达散射截面

矩量法是一种可以精确分析目标雷达散射截面的数值计算积分方程方法.但随着目标电尺寸的增大,所需存储空间和计算复杂度也急剧增加,以至超出了单机的内存容量,无法在单台计算机上求解.为降低矩量法所需内存和计算量,出现了多种快速算法,例如快速多极子[1]、多层快速多极子[2]、自适应积分方法[3]、快速傅里叶变换法[4]、自适应交叉近似算法[5]等.快速多极子及多层快速多极子可以将存储量由O(N2)降到O(N1.5),计算量由直接解的O(N3)降到O(N log N),但它依赖于加法定理对格林函数的展开,因此,其公式的推导、执行及运算往往需要预先已知格林函数.自适应积分方法、快速傅里叶变换法可以在傅里叶空间完成矩量法求解中的矩阵矢量乘,从而避免将阻抗矩阵元素直接存储,所需内存可降为O(N log N),计算复杂度降低为O(k N log N),但它更适用于体积分方程,表面积分方程效果较差.

自适应交叉近似算法是利用线性相关性来对低秩矩阵进行压缩的,可将存储量和计算量降为O(N log N).它由Bebendorf在2000年首先提出[5],并迅速被运用到多种数值算法中.2005年Zhao等将自适应交叉近似算法引入矩量法,用于分析电磁辐射与散射[6].2011年Tamayo等更将自适应交叉近似算法拓展到多层自适应交叉近似算法的概念[7].自适应交叉近似算法的优点在于它是一种纯数学方法,不依赖于格林函数展开及积分方程、基函数,更容易应用到矩量法计算中.虽然自适应交叉近似算法可以极大地减小矩量法所需的内存空间,但计算机的内存资源毕竟有限且价格相对昂贵.结合核外技术,将经过自适应交叉近似算法压缩过的矩阵存储到拥有更大空间的硬盘上[8],求解时分块提取,逐块求解,可以进一步提升单台计算机的求解能力.

1 自适应交叉近似算法

自适应交叉近似算法是利用远场组所形成的阻抗矩阵的低秩特性,对其进行分解,形成一对小型的满秩矩阵块来代表矩量法中的远场互作用矩阵,从而有效地对远场子矩阵块进行压缩.Zm×n代表矩量法中两个远场组的互阻抗[9],自适应交叉近似算法即采用两个满秩矩阵乘积的形式构造来近似表达Zm×n,即

其中,r为矩阵Zm×n的有效秩,Um×r和Vr×n为两个满秩矩阵.秩r的选取根据下式得到[10]:

当Zm×n用Um×r和Vr×n两个矩阵表示时,存储量由m×n变为r×(m+n).若r×(m+n)＜m×n(通常r≪min(m,n)),则自适应交叉近似算法只需保存Um×r和Vr×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 核外存取

矩量法形成的阻抗矩阵是一个稠密阵,矩阵规模和每个元素的位置都是固定的,核外存储时只需顺序存储,在读取时可根据元素在矩阵中的位置推算它在核外文件中的起始地址.与矩量法不同,自适应交叉近似算法得到的阻抗矩阵的大小是不固定的,它将阻抗矩阵分为多个子矩阵,逐块计算,并根据远场互作用阻抗的低秩特性进行矩阵压缩.相互距离不同,各子矩阵的压缩程度不同,距离越远,压缩效果越好,而两个相邻区域的阻抗元素甚至不能压缩.这导致无法确定某一分组矩阵在核外文件中的起始地址,因此,需要建立一个数组记录每一个子矩阵的形态、起始地址以及是否进行了压缩.在内存分配一个三维数组ACAREC[N][N][6],其中N为分组数,第三维的6个元素分别记录该子矩阵在文件中的起始地址、长度、是否进行压缩以及压缩后的两个满秩矩阵的行列数m、r、n.阻抗矩阵填充完毕后,数组ACAREC记录了所有分组的存储信息,在计算时就可以通过数组中的信息逐个读取阻抗子矩阵[8].

2.2 核外求解

由于自适应交叉近似算法将阻抗矩阵分组计算,子矩阵在压缩后,由两个满秩矩阵组成,已经不再是原始阻抗矩阵的形式,因此,矩矢乘的计算必须采用逐块分步计算,将分步结果相加组成最终矢量的方式.核外求解并不改变这一过程,只是多了从硬盘读取数据的过程.

这里利用共轭梯度残差法(CGNR)进行核外求解.假设自适应交叉近似算法在矩阵填充时将阻抗矩阵A分为16个分组分别计算,那么在核外存储也是按照分组将矩阵分为16个子矩阵.CGNR在迭代过程中,需要阻抗矩阵参与计算的步骤是wi=Api和zi=AHri,即阻抗矩阵与矢量相乘和阻抗矩阵的共轭转置与矢量相乘.以wi=Api的计算为例,阻抗矩阵A在核外是按照分组存储的,因此,将相乘的矢量也相应分组,如式(3)将矩阵分为16个子矩阵,每个子矩阵用Aij表示,已知相乘矢量相应分为4个子矢量列,用pj表示,

则wi可通过处在第i行的子矩阵Aij分别与相应的子矢量列pj相乘后全部相加得到,如

如果Aij经过了压缩,是采用两个满秩矩阵近似的,那么式(4)可转化为

由于矩阵采用核外存储,每计算一个子矩阵的矩矢乘都需要读取一次核外文件,根据数组ACAREC记录的信息,提取出相应子矩阵,并将计算结果记录在内存.式(5)需要读取4次核外数据,整个阻抗矩阵的计算需读取16次,也就是分组个数.

zi=AHri的计算与上述过程类似,这里不再赘述.由于自适应交叉近似算法本身对阻抗矩阵进行了分组,所以核外求解时的分块计算并没有增加额外的计算量.

3 计算实例

计算如图1所示金属圆球的雷达散射截面(RCS),并与Mie级数对比以验证算法的准确性.球半径为1 m,剖分尺寸为0.06 m,剖分为2 724个三角形面片,未知数有4 086个.激励平面波的波长为1 m,由-z方向入射,沿x方向极化.如图1所示,核外自适应交叉近似算法、自适应交叉近似算法与矩量法相比,它们计算雷达散射截面(RCS)的结果一致,与Mie级数结果吻合良好,说明自适应交叉近似算法不损失矩量法计算精度,且核外计算不影响自适应交叉近似算法的计算结果.

表1体现了当物体剖分变密,未知量数目增大时运算过程所占内存和迭代求解时间的变化趋势.可以看出,矩量法的存储量增加趋势为O(N2),而交叉近似算法对内存的要求为O(N log N),自适应交叉近似算法对矩阵矢量乘的加速也使其迭代时间小于矩量法的计算时间.当矩阵规模增大时,自适应交叉近似算法优势显现.而核外自适应交叉近似算法由于每次计算只需存储一个子矩阵的数据,内存需求非常小.尽管核外读取数据需耗费一定时间,但结合自适应交叉近似算法,核外算法的计算效率仍优于矩量法.

图1 波长1 m球体x Oz面上归一化雷达散射截面

表1 球体雷达散射截面求解所需内存和迭代时间

为进一步验证算法求解电大问题的有效性和稳定性,增加球体的电尺寸,球半径为1 m,剖分为32 736个三角形面片,未知数49 104个.激励平面波的波长为0.25 m,由-z方向入射,沿x方向极化.计算此金属球矩量法理论需内存18.4 GB,采用自适应交叉近似算法及核外自适应交叉近似算法可以正常计算.如图2所示,核外自适应交叉近似算法、自适应交叉近似算法与Mie级数结果吻合良好,说明核外自适应交叉近似算法求解电大问题结果依然精确.

图2 波长0.25 m球体x Oz面上归一化雷达散射截面

图3 金属导弹x Oz面上雷达散射截面

接着验证算法计算复杂形状目标的有效性,计算一金属导弹模型如图3所示,电尺寸约14λ×12λ×3λ,剖分为30 780个三角形面片,未知数为46 170,入射波同上例.矩量法理论需内存16.26 GB,超过普通计算机物理内存,采用快速多极子算法需占用内存1.83 GB,而采用核外自适应交叉近似算法只需占用155 MB即可计算得到导弹的RCS,结果如图3所示.但是在计算时间上核外自适应交叉近似算法花费711 min,比快速多极子多耗时约80 min.这在一定程度上因为采用核外计算在硬盘存取数据上需花费一定时间,如何高效地存取数据是下一步研究的重点.

4 结 论

矩量法计算电大物体的雷达散射截面存在占用内存空间及计算量巨大的问题,自适应交叉近似算法可以有效地压缩阻抗矩阵,加速矩阵填充和矩阵向量乘,该运算可以提升矩量法的计算效率;采用核外技术可以进一步节省内存空间,扩大单台计算机的计算能力.计算结果表明,此方法有效地降低了矩量法所需内存和计算量,并且自适应交叉近似算法及核外计算不影响矩量法的计算精度.

[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