MLFMA_VIE_MoM大型矩阵方程的快速迭代求解方法

MLFMA/VIE2MoM大型矩阵方程的 快速迭代求解方法 王文博,徐金平 (东南大学毫米波国家重点实验室,江苏南京 210096) 摘 要: 本文针对体积分方程矩量法( VIE2MoM)分析三维非均匀介质电磁散射问题所导出的大型矩阵方程的 求解问题, 基于多层快速极子技术(MLFMA)算法研究了快速近似迭代方法. 提出了一种基于MLFMA 分组MATCH_ word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 _1714479177631_0对系数 矩阵进行重组并提取强耦合元素的近场预条件器的构造方法,有效地提高了广义最小余量法(GMRES)的迭代收敛速 度.提出了一种在迭代计算过程中的近似矩阵向量乘积方案,明显降低了单步计算过程中MLFMA 远区耦合作用的计 算时间.计算实例表明, 采用本文的迭代加速技术可使计算速度提高 3 至 5 倍,有效地提高了 VIE2MoM大型矩阵方程 的迭代求解速度. 关键词: 矩量法; 体积分方程; 多层快速多极子; 预条件; 近似迭代方法 中图分类号: TN011 文献标识码: A 文章编号: 037222112 ( 2010) 0922009205 A Fast Iterative Method for Solving Large Matrix Equations Generated by MLFMA/ VIE2MoM WANGWen2bo,XU Jin2ping ( State KeyLaboratory of Millimeter Waves, Southeast University, Nanjing, Jiangsu 210096, China ) Abstract: A fast iterative method based on the implementation of multilevelfast multiple algorithm(MLFMA) is proposed for solving the large scale matrix equation generated by the method of moment solution to volume integral equation( VIE2MoM) for 32 D inhomogeneous dielectrics. Firstly, the whole coefficient matrix elements are realigned based on the scheme of the groups of MLFMA. By extracting strong coupling elements, a fast method for constructing the near2field preconditioner is proposed to acceler2 ate the convergence rate when the matrix equation is solved by the generalized minimum residual (GMRES) algorithm. And then, an approximate method is put forward in partly iterative steps when the relative error reaches to a specific value, which shortens the computational time of the far field contribution during each iterative step. Numerical examples show that the combination use of these two fast methods can raise the speed of computation for 3 to 5 times, which is very effective to improve the efficiency of GM2 RES algorithm for large matrix equation solution. Keywords: method of moment; volume integral equation; multilevel fast multipoles algorithm; preconditioning technique; approximate iterative method 1 引言 三维非均匀介质体的电磁散射研究对于电磁隐身 技术、天线罩的设计、吸波屏的设计、地下目标探测技术 以及生物体的电磁建模等领域的发展都具有重要意义. 基于体积分方程的矩量法 ( VIE2MoM) [ 1]可以有效地处 理复合介质夹层等复杂结构,分析其电磁特性.应用矩 量法求解电磁问题时,其计算量主要体现在两方面:一 是系数矩阵的计算;二是求解大型矩阵方程的计算量. 传统矩量法计算量较大,当未知元数目较多时,往往需 要大量的计算机内存和计算时间. 而且对于 VIE2MoM 来说,由于对介质体进行了体网格的剖分,其大大增加 的未知元数目在很大程度上限制了 VIE2MoM的应用. 随着电磁问题的复杂化,国外的很多学者对VIE及其与 快速方法的结合[ 2~ 4]开展了研究与应用,其中多层快速 多极子技术(MLFMA)能够将计算内存和计算复杂度降 低到 O(N log N) [ 5~ 7] .在矩阵求解方面, 由于直接求解 方法不适合大型矩阵方程的求解.因此一般都采用迭代 收稿日期: 2009204225;修回日期: 2010203210 基金项目:国家自然科学基金委创新群体基金(No. 606221002) 第 9期2010年 9月 电 子 学 报 ACTA ELECTRONICA SINICA Vol . 38 No. 9 Sep. 2010 方法来求解由MoM导出的稠密矩阵方程. 在众多的迭 代算法中,广义最小余量( GMRES)算法[ 8]比较适用于稠 密矩阵方程的快速求解.迭代求解的速度一般取决于 算法本身和矩阵方程的性态. 但是一般来说, VIE2MoM 导出的方程组性态比较差, 导致迭代方法收敛速度缓 慢.而且随着未知元数目的增加, 系数矩阵条件数增 大.另一方面GMRES算法随着迭代步数的增加,计算量 和内存需求量也会增加,尤其是当矩阵规模很大时,对 内存需求的大量增加会导致在单机上无法运行. 虽然 可以通过重启技术来克服这一困难, 但是会使迭代收 敛速度变慢,导致计算效率降低. 本文针对 VIE2MoM产生的大型矩阵方程, 在衡量 了计算量、内存需求以及迭代收敛加速效果后, 构造了 一种近场预条件器改善 GMRES算法的迭代收敛效率. 同时,在计算到一定精度后,采用了近似矩阵向量乘积 来代替原来的矩阵向量乘积, 既保证了计算精度,又减 少了单步迭代时间. 2 快速迭代算法的实现 211 近场预条件技术 为加快迭代求解的收敛速度,通过引入一个新的 矩阵对原有矩阵方程进行变换以改善系数矩阵条件数 是一种常见的手段.但是构造预条件器需要增加额外 计算量和内存需求,因此一个好的预条件器应该是在 它的构造过程中的计算时间和内存消耗不能太长,且 对计算迭代收敛有一定的加速效果. 本文针对研究非均匀介质目标时由VIE2MoM产生 的上万未知元数目的矩阵方程,在MLFMA算法的基础 上,通过选取位于系数矩阵对角块中具有强烈近场耦 合作用的单元作为一个近似矩阵,该近似稀疏矩阵反 映了系数矩阵的基本谱特征,其逆阵可作为矩阵方程 的预条件器,其构造过程为: (1)对未知元重新排序:按照MLFMA算法中最底 层分组的位置,将整个系数矩阵表示为分块矩阵的形 式.选取具有强耦合的近场作用的阻抗矩阵[ Z] G m , G m 构 成一个近似对角块阵作为ŽA: ŽA= [ Z] G1, G1 0 , , 0 0 w 0 , s s 0 [ Z] Gm, Gm 0 s s , 0 s 0 0 , , 0 [ Z] GN , GN (2)对 ŽA进一步稀疏化,在每个子矩阵[ Z] Gm, Gm中 根据基函数与权函数的距离筛选具有强耦合作用的近 场元素,得到一个稀疏化的大型近似对角阵 A. (3)采用递归 Cholesky分解算法[9]求解 A- 1, 最终 将 A- 1分解为一系列矩阵连乘的形式: A- 1= F N- 1 k= 1 Pk # F N k= 1 Lk # F N- 1 k= 1 Ok ( 1) 其中: 上三角阵 Pk = Ik- 1 0 0 0 1 - a- 1N+ 1- kuTN- k 0 0 IN- k , 下三角阵 Ok= PTk , aN+ 1- k为矩阵AN+ 1- k对角线上第一个元素, uN- k 为 ( N - k ) @ 1 阶 阵, 对 角 阵 Lk= Ik- 1 0 0 0 a - 1N+ 1- k 0 0 0 IN- k . 通过上述过程可以快速地构造出一个近似的近场 预条件器:首先 A中的元素在矩阵向量乘积之前已经计 算出来的,这里只需要根据判断条件对 A进行填充;在 求逆过程中式( 1)中的矩阵连乘不需预先计算出来,可 在方程求解过程中依次与向量做乘法操作,而且 A高度 稀疏化且近似于对角阵,其求逆运算可以快速的完成. 另一方面,构造该预条件器的内存消耗的代价比 较少,这主要是由于两方面的原因: ( 1) A 为高度稀疏 化矩阵,故采取了压缩存储的方式进行存储; ( 2)在递 归 Cholesky分解求逆的过程只需存储一个同样大小的 三角阵. 212 近似矩阵迭代求解过程 实施MLFMA后,在矩阵方程的迭代求解过程中矩 阵与向量乘积的过程被分解为两部分: 第一项表示近 区耦合;第二项为远区耦合, 是通过MLFMA的聚集、扩 散和转移过程完成的,并不直接计算出 Z farij . E j ZijI ( i)j = E j I 近区耦合 Znearij I ( k)j + E j I 远区耦合 Z farij I ( k )j 迭代过程中, 事实上在每个单步过程中要实现 MLFMA算法中的聚集、转移、扩散的过程. 当分析目标 电尺寸比较大时,当分组数目较多,单步迭代中矩阵向 量乘积过程消耗的时间比较长,而且随着迭代收敛速 度的变缓, 迭代步数增加, 整个迭代过程计算时间很 长. 考虑到在矩阵向量乘积过程中近场阻抗矩阵元素 是影响电流系数的主要因素, 为了减少矩阵向量乘积 的时间,本文采取了以下近似处理方法: 当在迭代误差下降到一个临界迭代误差前,按照 传统的矩阵向量乘积过程,分别计算近区和远区的贡 献; 当在迭代误差下降到一个临界迭代误差之后, 近 似认为: E j Zfarij I ( k+ 1)j I E j Z farij I ( k)j = W( k )i 2010 电 子 学 报 2010 年 W( k )i 在第k 步MLFMA计算完毕后以常量存储下来,则 在下面的迭代过程中矩阵与向量的乘积变为如下的过 程,并假设在第 m步达到计算要求精度: E j Z ijI j( k+ 1) U E j Zij nearI j( k+ 1) + Wi ( k ) E j Z ijI j( k+ 2) = E j Zij nearI j( k+ 2) + Wi ( k ) s E j Z ijI j( m) = E j Zij nearI j( m) + Wi ( k ) E j Z ijI j( m+ 1) = E j Zij nearIj (m+ 1) + E j Zijf arI j (m+ 1) 采用这样的方法,节省了大量的远区作用的部分 矩阵向量乘积的时间, 而通常近区耦合的矩阵向量乘 积的计算量在总计算量中的比例很少,因此在后期迭 代过程中大大提高了矩阵矢量相乘的计算效率. 3 数值结果与分析 以分析双层半球形介质壳和三层介质平板的 RCS 为例,应用本文所构造的预条件器对矩阵求解过程进 行了预条件处理, 并考察了在部分迭代过程中采用近 似矩阵向量乘积对矩阵求解过程的加速效果. 算例 1 计算电尺寸为 5K0 @014K0 @3K0的三层非 均匀有耗介质板(如图 1 所示)的散射特性.平面波- z 方向入射,电场 x 方向极化. E^r1= 3. 24- j0. 03888, E^r2= 1. 1- j0. 0055. 在该算例中 MLFMA/VIE2MoM导出的矩阵方程的 阶数为 28998, 计算时最底层分组尺度为 0125波长,预 条件处理的近场阈值为 011波长,其迭代收敛效果如图 2 所示.在 Inter(R) Core(TM) 2 CPUT7200, 210GHz的单机 上构造预条件器的时间约为 8s,增加的内存消耗约为 60Mb左右,为原来内存消耗的 7% . 迭代精度达到 5e- 2时(结果精度为 010001) ,远区 耦合的贡献用近似值计算, 近似的矩阵求解的结果与 传统的求解方法一致,如图 3所示. 表 1 中给出不同的计算方法下该算例的矩阵求解 所需的时间和迭代步数,其中方法 1 表示传统的 GM2 RES迭代求解过程,方法 2表示仅采用了预条件技术处 理的GMRES方法,方法 3 表示仅采用了远区耦合近似 计算的方法的GMRES方法,而方法 4 表示本文结合了 预条件和近似迭代过程的GMRES求解方法. 表 1 三层介质平板快速矩阵求解 迭代步数 总迭代时间 s) 方法 1 61 212 方法 2 34 122 方法 3 41 122 方法 4 22 71 从表 1中可以明显地看到:仅使用预条件技术矩阵 求解时间减少约 42% ;而近似迭代法通过减少单步迭 代时间,也将矩阵求解时间节省了 42% ; 预条件技术结 合近似迭代方法使GMRES求解时间减少了 66% . 算例 2 计算一不规则非均匀介质体的电磁散射特 性,其结构如图 4所示,平面波沿- Z方向入射.上下两层 介质体的厚度为 0105波长,其介电常数 E^r1= 2- j,中间一 层介质体的厚度为 011波长,介电常数为 E^r2= 3- j. 2011第 9 期 王文博:MLFMA/VIE2MoM大型矩阵方程的快速迭代求解方法 该算例由VIE2MoM导出的矩阵方程阶数为 32145, MLFMA方法分析时最小分组尺度为 0125波长, 采用预 条件处理(近场阈值为 011波长)后,其迭代收敛过程被 大大加速,如图 5所示, 构造预条件器的时间约为 27s, 增加的内存消耗仅为 90Mb左右,仅为原来内存消耗的 8% .当迭代精度达到 5e22 时(结果精度为 01001) ,远区 耦合的贡献用近似的方法计算. 单步迭代的时间由原 来的 5s 减少为 3s. 表 2 中给出了不同的计算方法下该算例的矩阵求 解所需的时间和迭代步数.可以看到: 仅使用预条件技 术矩阵求解时间减少约 40% ; 而近似迭代法通过减少 单步迭代时间;也将矩阵求解时间节省了 57% ; 预条件 技术结合近似迭代方法使 GMRES 求解时间减少了 7215% . 表 2 不规则结构算例的快速矩阵求解 迭代步数 总迭代时间( s) 方法 1 42 197 方法 2 24 119 方法 3 31 84 方法 4 20 54 算例 3 分析双层半球形介质壳的电磁特性,其内 外直径分别为2167K0、3133K0 ,内层厚度均01333K0外层 介电常数 E^r1= 2- j,内层介电常数为 E^r2= 3- j. 该算例中由 VIE2MoM 导出的矩阵方程阶数为 20438,MLFMA方法分析时最小分组尺度为 0125 波长, 采用预条件处理(近场阈值为 011波长)后,其迭代收敛 过程被大大加速,如图 7所示.构造预条件器的时间约 为 36s,增加的内存消耗仅为 30Mb 左右,仅为原来内存 消耗的 3% . 当迭代精度达到 5e22 时 (结果精度为 01001) ,远区耦合的贡献用近似的方法计算,单步迭代 的时间由原来的 6s减少为 3s. 从图 8 中所示结果中可 以看出,本文的近似迭代过程并未影响最后计算结果 的精度. 表 3 双层半球壳算例的快速矩阵求解 迭代步数 总迭代时间( s) 方法 1 181 1117 方法 2 61 383 方法 3 120 624 方法 4 38 218 表 3中统计了不同的计算方法下该算例的矩阵求 解所需的时间和迭代步数.从表 3 中数据可知:仅使用 预条件技术矩阵求解时间减少约 65% ; 而近似迭代法 通过减少单步迭代时间,将矩阵求解时间节省了 45% ; 当预条件和近似迭代技术结合应用GMRES算法时,矩 阵求解时间减少至传统GMRES的 1/ 5. 通过上述计算可以看到, 在求解上万阶的大型矩 阵时,本文构造的预条件因子对加快GMRES算法收敛 速度、减少迭代次数取得了明显的效果,且构造 A- 1时 间和内存消耗相对较少; 采用改进的矩阵向量乘积迭 代方法后,能够降低迭代过程中一部分的单步迭代时 间,且计算结果仍然保持稳定.将近似迭代与预条件的 结合后, 能够更进一步提高大型VIE2MoM矩阵方程的 2012 电 子 学 报 2010 年 求解效率. 4 结论 本文在 MLFMA有效分组的基础上构建了一种快 速实现的近场预条件器,结合MLFMA算法实现过程和 物理意义,在部分迭代过程中采用近似矩阵向量乘积 的方法.数值结果表明: 通过这两种技术的应用, 在不 影响计算精度的情况下, 明显加快了求解VIE2MoM大 型矩阵方程的迭代收敛速度,大大减少了方程求解计 算时间. 参考文献: [ 1] D H Schaubert, D R Wilton, A WGlisson. A tetrahedral mod2 eling method for electromagnetic scattering by arbitrary shaped inhomogeneous dielectric bodies [ J] . IEEE Trans Antennas Propagat, 1984 , 32(1) : 77- 85. [ 2] X C Nie, L W Li, N Yuan, et al. Precorrected- FFT solution of the volume integral equation for 32D inhomogeneous dielec2 tric objects [ J] . IEEE Trans on Antennas and Propagation, 2005, 53( 1) : 313- 320. [ 3] Z Zhang, Q Liu. A volume adaptive integral method (VAIM) for 32D inhomogeneous objects[ J] . IEEE Antennas and Wire2 less Propaation Letters, 2002, 1: 102- 105. [ 4] C C Lu. A fast algorithm based on volume integral equation for analysis of arbitrarily shaped dielectric radomes [ J ] . IEEE Trans on Antennas and Propagation, 2003, 51(3) : 606- 612. [ 5] 王浩刚, 聂在平, 王军. 对三维多层快速多极子方法中不 变项计算的优化[ J] .电子学报, 2000, 28 (9) : 105- 108. Wang Hao2gang, Nie Zai2ping, Wang Jun. Optimization of the computation of invariance term in MLFMA [ J] . Acta Electron2 ica Sinica, 2000, 28 (9) : 105- 108. ( in Chinese) [ 6] 王文博,徐金平. 电大三维非均匀介质体散射特性的快速 分析[ J] .东南大学学报, 2008, 38(2) : 201- 205. WangWenbo, Xu Jinping. Fast analysis of the RCS of electri2 cally large 32D inhomogeneous objects[ J] . Journal of Southeast university, 2008, 38( 2) : 201- 205. ( in Chinese) [7] 胡俊, 聂在平,雷霖, 等.多层快速多极子方法中转移因子 的修正拉格朗日内插技术 [ J] . 电子学报, 2006, 34( 3) : 539 - 542. Hu Jun, Nie Zai2ping; Lei Lin, et al. Modified Lagrange inter2 polation technique for translation operators in multilevel fast multipole algorithm ( MLFMA) [ J] . Acta Electronica Sinica, 2006, 34(3) : 539- 542. ( in Chinese) [8] Saad Y, Schultz M. GMRES: a generalized minimal residual al2 gorithm for solving non2symmetric linear systems[ J] . SIAM J Sci Stat Comput, 1986, 7( 3) : 856- 869. [9] 牛臻弋, 徐金平.稀疏化递归 Cholesky分解预条件技术加 速 PO0MoM问题的迭代求解 [ J] . 应用科学学报, 2006, 24 (5) : 479- 484. 作者简介: 王文博 女, 1979 年生于山东烟台, 东南 大学毫米波国家重点实验室讲师.研究方向为天 线、电磁仿真计算及电磁兼容分析. E2mail:wbang@seu. edu. cn 徐金平 男, 1962年生于江苏, 东南大学毫 米波国家重点实验室教授、博士生导师,主要研 究方向为计算电磁学、电磁散射、天线与电磁兼 容、毫米波与亚毫米波理论与技术等. 2013第 9 期 王文博:MLFMA/VIE2MoM大型矩阵方程的快速迭代求解方法