[word doc]VIE-MoM大型矩阵方程的快速迭代求解方法

[word doc]VIE-MoM大型矩阵方程的快速迭代求解方法 VIE-MoM大型矩阵方程的快速迭代求解方 法 第9期 2010年9月 电子 ACTAElCrR0NICASINICA Vo1.38No.9 Sep.2010 MLFMA/VIE—MoM大型矩阵方程的 快速迭代求解方法 王文博,徐金平 (东南大学毫米波国家重点实验室,江苏南京210096) 摘要:本文针对体积分方程矩量法(VIE—MoM)分析三维非均匀介质电磁散射问题所导出的大型矩阵方程的 求解问题,基于多层快速极子技术(MLVMA)算法研究了快速近似迭代方法.提出了一种基于MlMA分组方案对系数 矩阵进行重组并提取强耦合元素的近场预条件器的构造方法,有效地提高了广义最小余量法(GMRES)的迭代收敛速 度.提出了一种在迭代计算过程中的近似矩阵向量乘积方案,明显降 低了单步计算过程中MLFMA远区耦合作用的计 算时间.计算实例表明,采用本文的迭代加速技术可使计算速度提高 3至5倍,有效地提高了VIE—MoM大型矩阵方程 的迭代求解速度. 关键词:矩量法;体积分方程;多层快速多极子;预条件;近似迭代方法 中图分类号:TN011文献标识码:A文章编 号:0372—2112(2010)09—2009—05 AFastIterativeMethodforSolvingLargeMatrixEquations GeneratedbyMLFMA/VIE-MoM WANGWen—bo,XUJin—ping (State撕 LaboratoryofMillimeterWaves,SoutheastUniversity,Nanfing,Jiangsu210096,China) Abstract:Afastiterativemethodbasedontheimplementationofmultilevelfastmultiplealgofithm(MLFMA)isproposedfor solvingthelargescalematrixequationgeneratedbythemethodofmomentsolutiontovolumeintegralequation(VIE-MoM)for3一 Dinhomogeneousdielectrics.Firstly,thewholecoefficientmatrixelementsarerealignedbasedontheschemeofthegroupsof MLFMA.Byex~acfings~ongcouphngelements,afastmethodforconstructingthenear-fieldpreconditionerisproposedtoacceler— atetheconvergenceratewhenthematrixequationissolvedbythegeneralized minimumresidual(GMRES)algorithm.Andthen, anapproximatemethodisputforwardinpartlyiterafivestepswhentherelativeerrorreachestoaspecificvalue,whichshortensthe computationaltimeofthefarfieldcontributionduringeachiterativestep.Numericalexamplesshowthatthecombinationuseof thesetwofastmethodsCanraisethespeedofcomputationfor3to5times,whichisveryeffectivetoimprovetheefficiencyofGM— RESalgorithmforlargematrixequationsolution. Keywords:methodofmoment;volumeintegralequation;multilevelfastmultipolesalgorithm;preconditioningtechnique; approximateiterativemethod 1引言 三维非均匀介质体的电磁散射研究对于电磁隐身 技术,天线罩的设计,吸波屏的设计,地下目标探测技术 以及生物体的电磁建模等领域的发展都具有重要意义. 基于体积分方程的矩量法(VIE—MoM)可以有效地处 理复合介质夹层等复杂结构,分析其电磁特性.应用矩 量法求解电磁问题时,其计算量主要体现在两方面:一 是系数矩阵的计算;二是求解大型矩阵方程的计算量. 收稿日期:2009—04—25;修回日期:2010.03.10 基金项目:国家自然科学基金委创新群体基金(No.606221002) 传统矩量法计算量较大,当未知元数目较多时,往往需 要大量的计算机内存和计算时间.而且对于VIE—MoM 来说,由于对介质体进行了体网格的剖分,其大大增加 的未知元数目在很大程度上限制了VIE—MoM的应用. 随着电磁问题的复杂化,国外的很多学者对VIE及其与 快速方法的结合J开展了研究与应用,其中多层快速 多极子技术(MIA)能够将计算内存和计算复杂度降 低到0(NlogN)一-7].在矩阵求解方面,由于直接求解 方法不适合大型矩阵方程的求解.因此一般都采用迭代 2010电子2010年 方法来求解由MoM导出的稠密矩阵方程.在众多的迭 代算法中,广义最小余量(GMRES)算法l_8J比较适用于稠 密矩阵方程的快速求解.迭代求解的速度一般取决于 算法本身和矩阵方程的性态.但是一般来说,V1E—MoM 导出的方程组性态比较差,导致迭代方法收敛速度缓 慢.而且随着未知元数目的增加,系数矩阵条件数增 大.另一方面GMRES算法随着迭代步数的增加,计算量 和内存需求量也会增加,尤其是当矩阵规模很大时,对 内存需求的大量增加会导致在单机上无法运行.虽然 可以通过重启技术来克服这一困难,但是会使迭代收 敛速度变慢,导致计算效率降低. 本文针对VIE.MoM产生的大型矩阵方程,在衡量 了计算量,内存需求以及迭代收敛加速效果后,构造了 一 种近场预条件器改善GMRES算法的迭代收敛效率. 同时,在计算到一定精度后,采用了近似矩阵向量乘积 来代替原来的矩阵向量乘积,既保证了计算精度,又减 少了单步迭代时间. 2快速迭代算法的实现 2.1近场预条件技术 为加快迭代求解的收敛速度,通过引人一个新的 矩阵对原有矩阵方程进行变换以改善系数矩阵条件数 是一种常见的手段.但是构造预条件器需要增加额外 计算量和内存需求,因此一个好的预条件器应该是在 它的构造过程中的计算时间和内存消耗不能太长,且 对计算迭代收敛有一定的加速效果. 本文针对研究非均匀介质目标时由VIE.MoM产生 的上万未知元数目的矩阵方程,在MLFMA算法的基础 上,通过选取位于系数矩阵对角块中具有强烈近场耦 合作用的单元作为一个近似矩阵,该近似稀疏矩阵反 映了系数矩阵的基本谱特征,其逆阵可作为矩阵方程 的预条件器,其构造过程为: (1)对未知元重新排序:按照MLFMA算法中最底 层分组的位置,将整个系数矩阵表示为分块矩阵的形 式.选取具有强耦合的近场作用的阻抗矩阵[z]..构 成一个近似对角块阵作为A: A= (2)对进一步稀疏化,在每个子矩阵[z].中 根据基函数与权函数的距离筛选具有强耦合作用的近 场元素,得到一个稀疏化的大型近似对角阵A. (3)采用递归choleskv分解算法求解A一,最终 将A分解为一系列矩阵连乘的形式: 一 1?,1 A一=?-?-nO(1) k=lk=lk=l 其中: 『一00] 上三角阵=101一?1一一I,下三角阵l 00一J Ok=P{,n?+l一为矩阵A?+l—对角线上第一个元素, U?一 为(N,k)×1阶阵,对角阵 r一100] L=f0aN1一k01.1 00IN一J 通过上述过程可以快速地构造出一个近似的近场 预条件器:首先A中的元素在矩阵向量乘积之前已经计 算出来的,这里只需要根据判断条件对A进行填充;在 求逆过程中式(1)中的矩阵连乘不需预先计算出来,可 在方程求解过程中依次与向量做乘法操作,而且A高度 稀疏化且近似于对角阵,其求逆运算可以快速的完成. 另一方面,构造该预条件器的内存消耗的代价比 较少,这主要是由于两方面的原因:(1)A为高度稀疏 化矩阵,故采取了压缩存储的方式进行存储;(2)在递 归Cholesky分解求逆的过程只需存储一个同样大小的 三角阵. 2.2近似矩阵迭代求解过程 实施MLFMA后,在矩阵方程的迭代求解过程中矩 阵与向量乘积的过程被分解为两部分:第一项表示近 区耦合;第二项为远区耦合,是通过MLFMA的聚集,扩 散和转移过程完成的,并不直接计算出z. ?z=?z+?z 迭代过程中,事实上在每个单步过程中要实现 MLFMA算法中的聚集,转移,扩散的过程.当分析目标 电尺寸比较大时,当分组数目较多,单步迭代中矩阵向 量乘积过程消耗的时间比较长,而且随着迭代收敛速 度的变缓,迭代步数增加,整个迭代过程计算时间很 长. 考虑到在矩阵向量乘积过程中近场阻抗矩阵元素 是影响电流系数的主要因素,为了减少矩阵向量乘积 的时间,本文采取了以下近似处理方法: 当在迭代误差下降到一个临界迭代误差前,按照 传统的矩阵向量乘积过程,分别计算近区和远区的贡 献; 当在迭代误差下降到一个临界迭代误差之后,近 似认为: ?tj-j’川’??一zfe11?= 』J 0O Z 一一0;0 一O0一 Z 0 . .0,一 O;0 Z 第9期王文博:MLFMA/VIE-MoM大型矩阵方程的快速迭代求解方 法 在第k步MLFMA计算完毕后以常量存储下来,则 在下面的迭代过程中矩阵与向量的乘积变为如下的过 程,并假设在第m步达到计算要求精度: ?’m)=?z’m)+’ ?z’m+1]:?”‘‘m+1)+?z’) 采用这样的方法,节省了大量的远区作用的部分 矩阵向量乘积的时间,而通常近区耦合的矩阵向量乘 积的计算量在总计算量中的比例很少,因此在后期迭 代过程中大大提高了矩阵矢量相乘的计算效率. 3数值结果与分析 以分析双层半球形介质壳和三层介质平板的RCS 为例,应用本文所构造的预条件器对矩阵求解过程进 行了预条件处理,并考察了在部分迭代过程中采用近 似矩阵向量乘积对矩阵求解过程的加速效果. 算例1计算电尺寸为520×0.42o×320的三层非 均匀有耗介质板(如图1所示)的散射特性.平面波一z 方向入射,电场方向极化.l=3.24一i0.03888,;r2= 1.1一j0.0055. 在该算例中M~VIE—MoM导出的矩阵方程的 阶数为28998,计算时最底层分组尺度为0.25波长,预 条件处理的近场阈值为0.1波长,其迭代收敛效果如图 2所示.在Inter(R)Core(TM)2CPUT7200,2.0GHz的单机 上构造预条件器的时间约为8s,增加的内存消耗约为 60Mb左右,为原来内存消耗的7%. 图1三层非均匀 介质平板 jterativenglnbers 图2三层介质平板的迭代收敛效果 迭代精度达到5e一2时(结果精度为0.0001),远区 耦合的贡献用近似值计算,近似的矩阵求解的结果与 传统的求解方法一致,如图3所示. 表1中给出不同的计算方法下该算例的矩阵求解 所需的时间和迭代步数,其中方法1表示传统的GM. RES迭代求解过程,方法2表示仅采用了预条件技术处 理的GMRES方法,方法3表示仅采用了远区耦合近似 计算的方法的GMRES方法,而方法4表示本文结合了 预条件和近似迭代过程的GMRES求解方法. theta/(.)phi-~)0 图3非均匀介质平板的散射场 表1三层介质平板快速矩阵求解 迭代步数总迭代时间s) 方法161212, 方法234122 方法341l22 方法42271 从表1中可以明显地看到:仅使用预条件技术矩阵 求解时间减少约42%;而近似迭代法通过减少单步迭 代时间,也将矩阵求解时间节省了42%;预条件技术结 合近似迭代方法使GMRES求解时间减少了66%. 算例2计算一不规则非均匀介质体的电磁散射特 性,其结构如图4所示,平面波沿一z方向入射.上下两层 介质体的厚度为0.05波长,其介电常数=2一j,中间一 层介质体的厚度为0.1波长,介电常数为=3一j. 图4非均匀介质体 ++ ++ ‘‘ 哪 ZZ ??, ?l1 ++ ZZ ?? 凳 /, 2012电子2010年 该算例由VIE—MoM导出的矩阵方程阶数为32145, MLFMA方法分析时最小分组尺度为O.25波长,采用预 条件处理(近场阈值为0.1波长)后,其迭代收敛过程被 大大加速,如图5所示,构造预条件器的时问约为27s, 增加的内存消耗仅为90Mb左右,仅为原来内存消耗的 8%.当迭代精度达到5e一2时(结果精度为0.001),远区 耦合的贡献用近似的方法计算.单步迭代的时问由原 来的5s减少为3s. iterativenumbers 图5不规则介质体算例的迭代收敛效果 theta/() 图6采用近似迭代过程前后的归一化散射场 表2中给出了不同的计算方法下该算例的矩阵求 解所需的时问和迭代步数.可以看到:仪使用预条件技 术矩阵求解时问减少约40%;而近似迭代法通过减少 单步迭代时问;也将矩阵求解时问节省了57%;预条件 技术结合近似迭代方法使GMRES求解时间减少了 725%. 表2不规则结构算例的快速矩阵求解 I迭代步数I总迭代时间(s) 方法142197 方法2241l9 方法3l31I84 方法4I20l54 算例3分析双层半球形介质壳的电磁特性,其内 外直径分别为2.673.33.,内层厚度均0.33320外层 介电常数=2一i,内层介电常数为r2=3一 该算例中由VIE—MoM导出的矩阵方程阶数为 20438,MLFMA方法分析时最小分组尺度为0.25波长, 采用预条件处理(近场阈值为0.1波长)后,其迭代收敛 过程被大大加速,如图7所示.构造预条件器的时间约 为36s,增加的内存消耗仅为30Mb左右,仅为原来内存 消耗的3%.当迭代精度达到5e一2时(结果精度为 0.001),远区耦合的贡献用近似的方法计算,单步迭代 的时间由原来的6s减少为3s.从图8中所示结果中可 以看出,本文的近似迭代过程并未影响最后计算结果 的精度. iterativenumbers 图7双层半球壳算例的迭代收敛效果 theta/(.) 图8采用近似迭代过程前后的RCS值 表3双层半球壳算例的快速矩阵求解 迭代步数总迭代时间(S) 方法118111l7 方法26】383 方法3120624 方法438218 表3中统计了不同的计算方法下该算例的矩阵求 解所需的时问和迭代步数.从表3中数据可知:仅使用 预条件技术矩阵求解时间减少约65%;而近似迭代法 通过减少单步迭代时间,将矩阵求解时间节省了45%; 当预条件和近似迭代技术结合应用GMRES算法时,矩 阵求解时间减少至传统GMRES的1/5. 通过上述计算可以看到,在求解上万阶的大型矩 阵时,本文构造的预条件因子对加快GMRES算法收敛 速度,减少迭代次数取得了明显的效果,且构造A时 问和内存消耗相对较少;采用改进的矩阵向量乘积迭 代方法后,能够降低迭代过程中一部分的单步迭代时 问,且计算结果仍然保持稳定.将近似迭代与预条件的 结合后,能够更进一步提高大型VIE—MoM矩阵方程的 第9期王文博:MLFMA/VIE-MoM大型矩阵方程的快速迭代求解方法2013 求解效率 4结论 本文在MLFMA有效分组的基础上构建了一种快 速实现的近场预条件器,结合MLFMA算法实现过程和 物理意义,在部分迭代过程中采用近似矩阵向量乘积 的方法.数值结果表明:通过这两种技术的应用,在不 影响计算精度的情况下,明显加快了求解VIE—MoM大 型矩阵方程的迭代收敛速度,大大减少了方程求解计 算时间. 参考文献 [1]DHSchaubert,DRWilton,AWGlisson.Atetrahedralmod— efingmethodforelectromagneticscatteringbyarbitraryshaped inhomogeneousdielectricbodies[J].IEEETransAntennas Propagat,1984,32(1):77—85. [2]XCNie,LWLi,NYuan,eta1.Precorrected—Fsolution ofthevolumeintegralequationfor3一Dinhomogeneousdielec— tricobjectslJj.IEEETransonAntennasandPropagation, 2005,53(1):313—320. 13jZZhang,QLiu.Avolumeadaptiveintegralmethod(VA1M) f_or3一Dinhomogeneousobjects[J].—IEE—EAntennasand?rire— lessPropaationLetters,2002,1:102—105. 14JCCLu.Afastalgorithmbasedonvolumeintegralequationfor analysisofarbitrarilyshapeddielectricradomes[J].IEEE TransonAntennasandPropagation,2003,51(3):606—612. [5]王浩刚,聂在平,王军.对三维多层快速多极子方法中不 变项计算的优化[J].电子,2000,28(9):105—108. WangHao-gang,NieZai—ping,WangJun.Optimizationofthe computationofinvarianceterminMLFMAlJJ.ActaElectron— icaSinica,2000,28(9):105—108.(inChinese) [6]王文博,徐金平.电大三维非均匀介质体散射特性的快速 分析[J].东南大学,2008,38(2):201—205. WangWenbo,XuJinping.FastanalysisoftheRCSofelectri— callylarge3-Dinhomogeneousobjects[JJ.JournalofSoutheast university,2008,38(2):201—205.(inChinese) [7]胡俊,聂在乎,雷霖,等.多层快速多极子方法中转移因子 的修正拉格朗日内插技术[J].电子,2006,34(3):539 — 542. HuJun,NieZai—ping;LeiLin,eta1.ModifiedLagrangeinter— polationtechniquefortranslationoperatorsinmultilevelfast multipolealgonthrn(MLFMA)lJj.ActaEleclronicaSinica, 2006,34(3):539—542.(inChinese) [8]SaadY,SchultzM.GMRES:ageneralizedminimalresidualal— gorithmforsolvingnon-symmetricfinearsystemslJj.SIAMJ SciStatComput,1986,7(3):856—869. [9]牛臻弋,徐金平.稀疏化递归Cholesky分解预条件技术加 速POOMoM问题的迭代求解[J].应用科学,2006,24 (5):479—484. 作者简介 王文博女,1979年生于山东烟台,东南 大学毫米波国家重点实验室讲师.研究方向为天 线,电磁仿真计算及电磁兼容分析. E—mail:wbang@seu.edu.cn 徐金平男,1962年生于江苏,东南大学毫 米波国家重点实验室教授,博士生导师,主要研 究方向为计算电磁学,电磁散射,天线与电磁兼 容,毫米波与亚毫米波理论与技术等.