MLSSM算法实现网格离散复杂目标的优化设计

徐莉　潘宏　孙洪艳

摘 要： 为改进三维大尺寸复杂物体电磁建模精确求解的效率，采用了自适应交叉算法（ACA）基础上的多层简易矩阵稀疏算法（MLSSM）改进的方式，通过算法的理论及实现过程分析在实验验证中表明：应用的改进ACA算法计算效率比矩量法逐点计算显著提高；改进的MLSSM的内存需求减少了一半左右，矩阵构造过程速度有了明显提高；改进的MLSSM降低了计算复杂度，迭代求解过程速度有了明显提高。从算法对比结果可以看出，改进的MLSSM在降低计算复杂度方面占据优势，在分析半空间上大目标复杂物体优势明显。这一研究对复杂物体的电磁建模优化具有一定的理论和应用意义。

关键词： 电磁建模； 精确求解； 复杂物体； 多层简易矩阵稀疏算法； 自适应交叉算法

中图分类号： TN911.7?34 文献标识码： A 文章编号： 1004?373X（2016）07?0161?06

Abstract： To improve the efficiency of exactly solving the electromagnetic modeling of large?size three?dimensional complex object， the improved multilayer simple sparse matrix （MLSSM） algorithm based on adaptive crossover algorithm （ACA） is adop?ted. The experimental verification of theory analysis and realization process shows that： the computing efficiency of using improved ACA algorithm is significantly increased than that of moment method； the memory requirement is reduced by a half by means of the improved MLSSM， which can significantly improve the speed of matrix construction process； the computing complexity is reduced by means of the improved MLSSM， and the speed of iterative solution process is significantly improved. The comparison results show that the improved MLSSM algorithm has the advantages in the aspects of reducing the computing complexity and analyzing the large complex object in half space. The study has certain theoretical and applied significances for the optimization of the complex object electromagnetic modeling.

Keywords： electromagnetic modeling； exact solution； complex object； multilayer simple sparse matrix algorithm； adaptive crossover algorithm

0 引 言

随着科技不断的飞速发展，对三维电较大对象的电磁建模，同时还做数值分析方面的深层研究，借助于计算机软件以及硬件功能都得到了很大的提升，这让从前没办法对某些对象做研究分析，而在现在能够得以实现[1?3]。在现实社会中对于很大尺寸对象的研究分析预期借助计算机的功能水平大大高于实际发展的水平，所以如何提升数值运算的能力，是学者研究电磁学的关键因素。在三维电大尺寸对象的理论分析里，一般经常用到的方法有微分、高频等方法[4?5]。比如有限元法属于微分法，物理光学法、几何绕射理论属于高频方法。采用有限元方法虽能形成不太密集的矩阵，但其对欲求的对象做体剖分[6?7]。在分析对象的电尺寸非常大时，网格在离散时产生的未知量数目很多且无法预知，所以造成的运算量非常大。在高频条件下的假设，高频方法在面向较为复杂的对象时没办法得到精确的数据，所以无法应用[8]。而采用矩量法能够得到精确的数据，任意几何形状以及复杂的物体都能适用，也不用增加吸收边界条件，在做网格离散的时候，只用在被分析对象的表面上实施就可以，这样一来，该算法的未知数就大大减少。传统的矩量法得到的是稠密矩阵，在进行运算时会花费较多的时间以及空间，而当代的计算机要实现大尺寸对象运算非常困难[9?10]。本文基于上述背景，改进多层简易矩阵稀疏算法实现网格离散复杂目标的优化设计，这一研究对于复杂物体的电磁建模的优化有一定的理论和应用意义。

1 MLSSM算法改进设计

一开始的多层简易矩阵稀疏方法（MLSSM）是以直接的方法做求解的。该方法基于稀疏阻抗矩阵，而如今已成为迭代求解的方法，能够在低秩类方法上构建起来。另外，还可以把阻抗矩阵用另外几个更稀疏的矩阵以乘积的方式表达，其实就是低秩方法的再压缩。以常见的低秩类方法产生的阻抗矩阵里，层和层无逻辑上的关系，每一层都相互独立，并且在压缩以后矩阵的秩只可以在某种角度上减小以及对中间范围的电尺寸对象特征的分析。多层简易矩阵稀疏的任意一层阻抗矩阵都是环环相扣的，产生的是嵌套结构，所以只能再减小内存的需要以及提升矩阵矢量乘的处理。

1.1 自适应交叉算法（ACA）

同时把其代到式（4）能求得指定的频带内任何范围的频率点的未知向量解[x（k）]。在进行求解时仅作一次矩阵求逆运算，就能够得到全部频带内的频率响应。该优点就是ACA算法能够使得运算效率提升。

1.2 应用ACA优点改进多层简易矩阵稀疏方法

依照树形结构，可以把阻抗矩阵分成近场[ZN]和远场[ZF，]和其他快速算法不一样的是，多层简易矩阵稀疏方法把阻抗矩阵分成3部分。在其中任意一层的全部非空组，其阻抗元素有近场、本层远场以及父层远场3部分。在这里以一个四层八叉树形成的阻抗矩阵为例。四层树形结构的最细层的阻抗矩阵分解见图1。

图1右边第一个子图是描述近场组作用产生的矩阵。第二个子图是本层远场组对应的阻抗矩阵。第三个子图是父层远场组相互作用产生的矩阵。对于强相互作用的矩阵无需任何操作，采用矩量法做填充。弱相互作用部分采用ACA算法，MLSSM通过低秩类方法做填充。通常情况下，MLSSM可形成下面的递归表达式：

式中：[ZL]是在第[L+1]层远场部分阻抗矩阵的稀疏描述方式，其任意一层的阻抗矩阵都有其对应的本层以及父层远场；[ULZL-1VHL]是父层远场部分；[ZL]是本层远场部分，表示的是几个稀疏矩阵相乘。当创建一层数为[L]的树形结构时，最细层[ZL]描述的是近场组的阻抗矩阵，而在最粗层是没父层远场，因此，MLSSM由第[L]层递归到第2层。此时的矩阵元素全部是在复数域范围里，[UL]称作行基矩阵，[VL]称作列基矩阵，[UL，VL]都是以对角方式的酉矩阵。和传统的MLSSM对照，经改进后的MLSSM只用保存[UL]以及[12]的[ZL-1，]这样就减少了冗余的数据。按照这个方式，可以构造出和前面阻抗矩阵类似的表达式。

1.3 算法改进设计详细说明

按照改良的MLSSM本质思路，它的阻抗矩阵的表达式和MLSSM不一样，这里叙述其构造方法以及步骤。

耦合矩阵也涵盖了对应的本层远场和父层远场。本层远场可形成最细层的耦合矩阵，父层远场是下一层要操作的，在经处理后可形成嵌套形式。

改进的MLSSM构造的步骤（如图2所示）有下面三步：

（1） 在树形结构的底层，通过采用ACA算法，可把全部远场的阻抗矩阵做填充处理，得到子块的[Uij]以及[VHij，]其全部是低秩矩阵，近场的阻抗矩阵可采用矩量法求得。

（2） 把前面的[Uij]按照非空组做组合，同时进行SVD分解后乘以[VHij，]采用式（12）的方法最后得到最细层的行基、列基矩阵以及耦合矩阵。

（3） 耦合矩阵分为两个组成部分，把本层远场部分进行存储，父层远场部分做UV分解处理，最终得到如同第一个步骤的两个低秩矩阵相乘的表达式，即是次细层每个非空组的矩阵，反复进行前面叙述的步骤，一直到最粗层终止。

2 算法改进的实验验证

2.1 ACA算法优势验证

由上面叙述的最终数据结果可知如下结论：

（1） 泰勒级数展开和帕德逼近都在一定范围内的频带和矩量法解一致，而帕德逼近比泰勒展开近似频带更宽，和理论分析一样，预期效果也基本一致。

（2） 采用ACA算法可以较好的逼近双负媒质的MOM逐点运算解。表1说明了ACA算法能更好的得到双负媒质的宽频RCS频率响应，其效率比矩量法逐点的方式进行运算提升了很多。

2.2 压缩效果的对比验证

要证明经改进的MLSSM比传统的MLSSM对ACA压缩的效果更加明显，本文给出了几个数据进行验证。这几个数例在测试过程中，都在同一计算机设备配置下进行。最初，为保证实验流程的准确，还对一个半径为2.4 m的金属球进行了测试，预设的平面波入射频率是300 MHz，其波长[λ=1 m，]入射角[θi=0°，][?i=0°。]依据[0.1λ]的标准采取RWG基函数的方式将其表面做网格离散处理，之后未知量有23 952个。构建一个三层的树形结构，设置[0.3λ]为其最细层的电尺寸。再进行阻抗矩阵填充，ACA的截断公差是[1×10-3，]而MLSSM、改进的MLSSM的奇异值分解截断参数都一样，也是[1×10-3。]最后生成的方程组通过以GMRES方式进行迭代求解，设定收敛精度为[1×10-3。]此时，这两种方式都各自计算金属球的双站RCS，同时把这种结构以及Mie级数做对比，能够发现数据结果是吻合的，由此证明本文的运算结果是对的，如图5所示。表2将MLSSM与改进的MLSSM需占据的内存以及在进行迭代时耗费的时间做对照，能够知晓改进的MLSSM所需空间减少了一半，并且矩阵的构造提高了效率。

接着，分析如图6所示的自由空间导弹模型的散射特性。其电尺寸是[16λ，]平面波入射频率[f]为800 MHz，其波长为[λ=0.375 m，]入射角[θi=0°，?i=0°，]依据[0.1λ]的标准采取RWG基函数的方式将其表面做网格离散处理，之后未知量有56 859个。再进行阻抗矩阵填充，ACA的截断公差是[1×10-3，]而MLSSM、改进的MLSSM的奇异值分解截断参数都一样，也是[1×10-3。]构建一个四层的树形结构对此模型做分组，最后生成的方程组通过以GMRES方式进行迭代求解，设定收敛精度为[1×10-3。]此时，这两种方式都各自计算此模型双站RCS，见图7，发现数据结果是吻合的。表3将MLSSM与改进的MLSSM在需占据的内存、构造时间以及在进行迭代时耗费的时间做对照，能够知晓改进的MLSSM的运算降低了难度，并且在矩阵的构造以及迭代运算上都提高了效率。

如果需要计算的对象在有耗半空间的上方，因为并矢格林函数具有较为复杂的形式，其计算采用快速多极子难度较大；加上快速多极子受到分组的限制，通常情况下，它有以下三个环节，即聚合、转移以及配置；如果分组过大，即便转移过程可正常进行，但在一定程度上会降低聚合与配置过程的效率；如果分组过小，情况刚好相反，其转移过程与计算相对会变得更加复杂，而聚合与配置过程则没有多大影响。因此，分组大小要恰当，这样快速多极子才发挥其最大的效率，通常最细层的电尺寸不能超过[0.2～0.4λ]这个范围。经过改进的MLSSM方法是基于ACA而建立的，属于纯代数方法，这点与ACA相同，并不只局限于格林函数的形式，它就是对矩阵的数学压缩，没有快速多极子聚合转移配置的过程，所以也不受限于分组。由以上两个优点可知，经过改进的MLSSM非常适用于对有耗半空间上目标的分析。

3 结 语

本文对矩量法中的快速迭代法进行了概括，着重对MLSSM的阻抗矩阵形式进行了分析，同时采取了一种新的方法作出了相应的改进，经过改进的MLSSM是对低秩类方法的进一步压缩，新的MLSSM计算相对要简单很多，其嵌套结构使矩阵矢量乘操作速度加快，数值算例分析对其正确性、有效性以及实用性进行了验证，与其他算法相比，它在很大程度上可以减少同一模型的计算量，而且还是代数类方法，就算没有使用格林函数的形式，也可不受分组的限制，在分析环境较为复杂的电磁问题中比较适用。

参考文献

[1] 王鼎，吴瑛.一种利用互耦矩阵稀疏性的阵列误差有源校正改进算法[J].信号处理，2009（9）：1414?1420.

[2] 杜吉祥，余庆，翟传敏.基于稀疏性约束非负矩阵分解的人脸年龄估计方法[J].山东大学学报（理学版），2010（7）：65?69.

[3] ZHANG Z C， HONG H S， WAI O W， et al. Parallel hydrodynamic finite element model with an N?Best refining partition scheme [J]. Chinese journal of oceanology and limnology， 2010， 28（6）： 1340?1349.

[4] 崔树标，张云，周华民，等.边界元矩阵稀疏化算法及其应用[J].上海交通大学学报，2008（10）：1618?1621.

[5] 彭志威，王波，保铮，等.矩阵稀疏化中的最优子波滤波器组设计[J].西安电子科技大学学报，1999（1）：35?40.

[6] ZHONG Weitao， SHAO Zhijiang， ZHANG Yuyue， et al. Applying analytical derivative and sparse matrix techniques to large?scale process optimization problems [J]. Chinese journal of chemical engineering， 2000， 8（3）： 212?217.

[7] 程耿东.线性规划在结构优化设计中的一个应用及其稀疏算法[J].大连工学院学报，1979（1）：22?31.

[8] REN Jianmin， ZHANG Yimen. A sparse matrix technique for simulating semiconductor devices and its algorithms [J]. Journal of electronics （China）， 1990， 7（1）： 77?82.

[9] ZHENG Xiaolang， YANG Yiwei. A sparse matrix model?based optical proximity correction algorithm with model?based mapping between segments and control sites [J]. Journal of Zhejiang University science C， 2011， 12（7）： 436?442.

[10] FAN P， CAO Z. A matrix algorithm for computing the free space distance of TCM signal sequences [J]. Journal of electronics （China）， 1997， 14（4）： 328?335.