（信号与信息处理专业论文）区域分解结合多层快速多极子并行技术.pdf

摘要区域分解结合多层快速多极了并行技术 摘要 军事民用技术的发展，迫切要求精确高效地分析电大尺寸复杂目标的散射特 性。而且这些电磁特性也一直是计算电磁学研究领域持久不衰的热点和难点。电 磁问题的高效求解包含精度、效率和低内存需求方面的含义。随着所需解决问题 的电尺寸的增大，单个个人计算机甚至服务器的速度和内存往往不能满足科学技 术和工程问题的需求，一个好的解决方案是使用并行计算技术。近年来，并行计 算技术已经越来越深入地应用到科学研究、工程技术以及电磁学等领域。 目前快速多极子方法和多层快速多极子方法已经广泛应用于各种复杂目标 的电磁辐射与散射分析。尤其是多层快速多极子方法是研究三维目标矢量散射 特性的一种高效数值求解方法，而且具有比较明显的并行性。根据这些特性， 本文实现了多层快速多极子的高效并行。 由于在分析电超大尺寸目标时，多层快速多极子算法的计算量和存储量仍 然很大。为了进一步减少并行中计算机所需的内存，我们将并行的多层快速多 极子算法嵌入到重叠型区域分解技术中，这一方案将目标结构表面分成若干子 区域，依次对每个区采用并行快速多极子技术。这样对于一个电大尺寸的结构， 只需存储和处理每个子区的未知量及少量的整体信息，大大节省了求解时的内 存消耗。 关键词：电磁学，多层快速多极子，并行计算，电磁散射，区域分解 a b s t r a c t 【墨：域分舻f 结合多层伙速多极了并行技术 a b s t r a c t w i t ht h ed e v e l o p m e n to ft e c h n o l o g yf o rm i l i t a r ya n dc i v i la p p l i c a t i o n ，t h e a c c u r a t ea n de f f i c i e n ta n a l y s i so fe l e c t r o m a g n e t i cs c a t t e r i n gf o re l e c t r i c a l l yl a r g e o b j e c t si su r g e n t l yr e q u i r e d s of a r ，i n t e n s i v ei n v e s t i g a t i o n sh a v eb e e nd o n et of i n d t h ef a s ta n da c c u r a t en u m e r i c a lm e t h o d st os o l v es u c hp r o b l e m s t h eh i g he f f i c i e n c y a n dl o wm e m o r yr e q u i r e m e n ta r eu s u a l l yr e g a r d e da st w od o m i n a n tc h a r a c t e r so ft h e f a s ta l g o r i t h m s w h e nt h ee l e c t r i cs i z eo fo b j e c t sb e c o m e sl a r g e r ，t h es p e e da n d m e m o r yo fc o m p u t e rc a nn o ts a t i s f yt h en e e d i n g w i t ht h ed e v e l o p m e n to fh a r d w a r e a n ds o f t w a r eo fc o m p u t e r ，p a r a l l e l c o m p u t i n gi sw i d e l yu s e d i nm a n yf i e l d so f s c i e n t i f i cc o m p u t i n ga n de n g i n e e r i n gt e c h n o l o g y f a s tm u l t i p o l em e t h o da n dm u l t i l e v e lf a s tm u l t i p o l ea l g o r i t h m ( m l f m a ) h a v e b e e nw i d e l yu s e df o rt h ee l e c t r o m a g n e t i cr a d i a t i o na n de l e c t r o m a g n e t i cs c a t t e r i n g f r o mc o m p l e xt a r g e t e s p e c i a l l y , m l f m ai sah i g he f f i c i e n tn u m e r i c a lm e t h o df o r v e c t o rs c a t t e r i n gc h a r a c t e r i s t i ca n a l y s i s i nt h i st h e s i s ，t h ep a r a l l e l i z e dv e r s i o no f m l f m ai ss t u d i e da n dr e a l i z e d i no r d e rt of u r t h e rr e d u c et h eh u g er e q u i r e m e n to fc p ut i m ea n dm e m o r yi nt h e a n a l y s i so fe l e c t r i c a l l yu l t r al a r g ec o m p l e xt a r g e t ，t h ep a r a l l e lm l f m aa r ec o m b i n e d w i t ht h eo v e r l a p p e dd o m a i nd e c o m p o s i t i o nt e c h n i q u e i nt h ea n a l y s i s ，t h eu n k n o w n s u r f a c ec u r r e n te l e m e n t so nt h eo b j e c ta r ed e c o m p o s e di n t os e v e r a ls u b d o m a i n s w h e no n es u b d o m a i ni ss o l v e db yp a r a l l e lm l f m a ，o n l yt h eq u a n t i t i e ss u c ha sn e a r f i e l da n df a rf i e l di n t e r a c t i o ni n s i d et h i ss u b d o m a i na r es t o r e di nr a mi na d d i t i o n w i t hal i t t l ei n f o r m a t i o no fe n t i r ed o m a i n ，h e n c et h em e m o r yc o s ti sl a r g e l yr e d u c e d k e yw o r d s ：e l e c t r o m a g n e t i c s ，m l f m a ，p a r a l l e lc o m p u t i n g ，e l e c t r o m a g n e t i c s c a t t e r i n g ，o v e r l a p p e dd o m a i nd e c o m p o s i t i o n i i 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 己在论文中作了明确的说明。 研究生签名：年 月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：年 月日 坝l ：论义区域分解结合多层快速多极了并行技术 1 绪论 随着计算机的应用同趋复杂，从数据处理，信息处理，知识处理到智能处理， 应用范围越来越广，处理问题的规模越来越大，因此对计算机的运算速度和处理 能力要求也越来越高。尤其是一些具有挑战意义的科学工程计算问题，如目前的 计算电磁学方法都强烈地依赖于可以利用的计算机资源。随着所需解决问题的电 尺寸的增大，单个计算机的速度和内存都远远不能满足科学技术和工程问题的需 求。 尽管现在的计算机比十年d 矿快了一百倍，但是科学家和工程师还需要更快的 速度，因为他们面临的问题十分复杂浩大，虽然已经对问题进行了大量的简化， 但是现在的计算机仍然需要数小时，数日甚至数周来完成他们的程序。可以预见， 当你的计算机运行程序时，速度大幅度提高，可以利用的内存也不断增大，过去 一些无法忍受的计算任务将变得可以接受。当然，计算机c p u 运行速度比以前 快了很多，但是对计算机速度与性能的迫切需要的工程和应用，使很多科学家和 工程师无法忍受慢慢的等待。 并行计算技术正是高效利用计算机资源，提高计算速度的一种有效方法，它 是把一个任务分配给并行计算机系统中的多个处理器，每一个处理器只需工作在 问题的一部分，以多个处理器的联合快速的模拟一个大问题。因为每一个处理器 的工作并不是完全独立的，所以各个部分之f 日j 的信息交换及交换信息量的大小是 由物理模型和所解决问题本身特性决定的。 并行计算机组使解决大规模数值计算问题成为可能，并被认为是科学家和工 程师用来解决各种领域的问题的标准方法。 网络并行计算是近几年国际上并行计算新出现的一个重要研究方向。也是热 门课题：网络并行计算就是利用互联网上的计算机资源实现所需问题的计算。这 种并行计算环境的显著优点是投资少见效快灵活性强等。由于科学计算的要 求。越来越多的用户希望能具有并行计算的坏境但是除了少数计算机用户外， 很多用户由于资金的不足而不能使用并行计算机。一旦实现网络并行计算，就可 以通过网络实现超级计算的目的，因此，就不必购买昂贵的并行计算机。 目前国内一般的应用单位都具有局域网或广域网。所以基本上具备网络计 算硬件环境。其次网络并行计算的系统软件m p i 是当日，j 国际上公认的一种消 息传递标准软件系统。有了它，就可以在不具备并行机的情况下进行并行计算、 由于该软件是免费软件，没有版权问题，可以从国际互联网上获取其代码及其相 应的辅助工具程序，这无疑是对我们程序设计带来方便。 l 绪论 硕l 。论文 1 1 并行系统构成 在一个并行处理系统中，应陔包含三个部分：并行机系统结构、并行软件和 并行算法。当一台并行机已经提供，软件已经基本配置好的情况下，如何充分发 挥并行效率，并行算法是一个决定性的因素。并行算法的好坏直接关系到并行系 统的使用效率。所谓并行算法是指解题方法的精确描述，它包括一组有穷的规则， 这些规则规定了解决某一特殊问题的一系列运算。并行算法要能在所选用的并行 系统上求解问题和处理数据。其形式是一些可同时执行的进程的集合，这些进程 相互作用和协调工作，实现对给定问题的求解。 不论采用何种途径实现并行算法，都有一些基本的公共因素必须考虑。( 1 ) 洞察并提取并行性：当针对一个具体问题设计并行算法时，如果求解该问题的串 行算法已知，则就以这个串行算法为分析的出发点。如果该串行算法中没有明显 的并行性，则应当利片j 已有的相关知识提取其内在的并行性。( 2 ) 必须考虑通信 丌销：在决定并行算法复杂性时，必须考虑通信丌销。这是因为有时通信复杂性 比计算复杂性还高。换句话说，处理机之间数据的调度、传输所花的时问比实际 计算时间还多。这就需要在设计时尽量采取简单的通讯方式，并使传输的数据量 尽可能小，而在分析并行性能时也不能忽视通信的丌销。( 3 ) 并行算法必须适合 于所选用的并行系统：并行算法直接依赖于并行处理系统，不同类型系统上的并 行算法有很大的区别。在开发时必须注意这一点。 并行算法可以用很多标准来评价，但通常人们最关心的是算法与它能求解的 问题的规模之间的关系。为此，对并行算法性能的评价通常采用以下基本参数： 加速比、效率、成本以及算法复杂性。 1 ) 并行算法加速比：算法在单处理机上的实际执行时间与使用p 台处理 机时算法的实际执行时问之比。 2 ) 并行算法的效率：最快的串行算法在单处理机上的实际执行时间与使 用p 台处理机时算法的实际执行时间之比。 3 ) 并行算法的成本：并行算法运行时间和算法所用机器台数的乘积。 4 ) 并行算法复杂性：求解规模为n 的问题所花费的运行时间t ( n ) 。当n 趋 近于无穷大时，时间复杂性的极限称为算法的渐进时间复杂性。 理想情况下加速比等于并行计算机的台数p ，但由于算法并行度不高以及通 讯和同步等时间的丌销，加速比是不可能达到p 的。研究并行算法的目的就在于 提高算法的加速比，降低时间复杂性。 对于本文论题来说，并行系统有以太网络连接的高性能的p c 机群，操作系 统为m i c r o s o f tw i n d o w sx p ；也有以服务器为并行平台的，操作系统为l i n u x 。 硕j ：论文 区域分解结合多层快速多极了并行技术 在并行计算系统中，一个可移植的、基于消息传递的并行编程平台是必不可 少的。消息传递编程是一种显式编程，大多数系统使用发送和接收函数来交换数 据。目前，在分布存储并行编程环境下已经存在许多通用且成熟的消息传递软件 包，其中m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 和p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 是 应用比较广泛的两种。基于m p i 可以提供一个实用的、可移植的、高效灵活的 接口库，所以在本论题中，选用m p i 为并行开发的软件平台 s i 。 1 2m p i 简介 m p i 是由研究实验室、大学和产业界联合研制的一个消息传递的标准。m p i 环境包括一个m p i 函数库，提供了上百个函数。在消息传递库方法的并行编程 中，一组进程所执行的程序是用标准串行语言书写的代码加上用于消息接收和发 送的库函数的调用。在绝大部分m p i 实现中，一组固定进程在程序初始化的时 候生成，一个处理器生成一个进程，这些进程可以执行相同或不同的代码。进程 间的通信可以是点对点的，也可以是群集的。目前，除了商业版本以外，在很多 网站上都可以下载到m p i 的多个由国际上一些研究团体开发的免费版本。 m p i 是一个库而不是一门语言。许多人认为m p i 就是一种并行语言这是不 准确的，但是按照并行语言的分类可以把f o r t r a n + m p i 或c + m p i 看作是一 种在原来串行语言基础之上扩展后得到的并行语言m p i 库可被 f o r t 凡蝌7 7 c f o r t r a n 9 0 c + + 调用。从语法上说它遵守所有对库函数过程的调用 规则和一般的函数过程没有什么区别。 m p i 是一种消息传递编程模型并成为这种编程模型的代表和事实上的标准。 m p i 虽然很庞大但是它的最终目的是服务于进程问通信这一目标的。 消息传递方式是广泛应用于多类并行机的一种模式，特别是那些分布存储并 行机，尽管在具体的实现上有许多不同，但通过消息完成进程通信的基本概念是 容易理解的，十多年来这种模式在重要的计算应用中已取得了实质进步。有效和 可移植地实现一个消息传递系统是可行的。因此通过定义核心库程序的语法语 义，这将在大范围计算机上可有效实现，将有益于广大用户。这是m p i 产生的 重要原因。 l 绪论硕i ：论义 i 3 并行平台及评价并行效率的标准 i 3 1 并行平台 硬件方面：教研室根据需求搭建了三个高性能高效率并行计算机平台，一个 是由十八台适合数值算法研究的高性价比的计算机( p e n t i u mi v2 8 g h z ，1 g 内 存，m i c r o s o f tw i n d o w sx p 操作系统) 组成，并选用传输速率为1 0 0 1 0 0 0 m b s 的千兆以太网络组成处理机群，具有良好的可复用性和可扩展性，适用于网络并 行计算的研究。另一个平台由十七台更新更高效计算机组成( p e n t i u mi v 双核 1 8 g h z ，2g 内存，m i c r o s o f tw i n d o w sx p 操作系统，千兆以太网) ，可以满足 更大规模未知量的计算。还有一台服务器，硬件配置( 双c p u l 6 g h z ，每个c p u 四核，1 6 g 内存，l i n u x 操作系统) ，同样可以满足大规模未知量的计算，且服务 器可以长时i 日j 稳定工作。 软件方面，选用围内外较为流行的m p i c h 2 版本的并行软件与f o r t r a n 语言 相结合进行并行程序设计，它具有通用性强，系统规模小，成熟度高，可以免费 获得等优点。 1 3 2 并行效率的评价 并行计算主要是为了解决串行程序计算速度或内存不足而设计的。因此对 并行效率的评价也因该根据实际需要从程序执行时间和单机内存的减少来判断。 加速比u o l 定义为 。 串行算法在处理机的执行时间 、 = 一 并行算法在具体育p 台处理机的系统上的执行时间 并行算法效率i t o l 定义为： e p = s p p 1 4 本文主要内容和章节构架 二十世纪六十年代，h a r r i n g t o n 等针对电场或磁场积分方程提出了矩量法。 自此以后，该方法无论在理论上还是技术上都得到了很大发展，并在工程上得到 了广泛的应用。但矩量法所产生的矩阵是满阵，存储量的量级是矩阵阶数的平方 o ( n 2 ) ，求其逆的计算量是矩阵阶数的立方d ( 3 ) ，即迭代求解的计算量是 4 硕上论文区域分解结合多层快速多极了并行技术 o ( n z 、。对电大尺寸目标而言，无论是存储量或计算量上，现有计算机资源难以 满足需求。一些大幅度降低内存的求解时i 日j 的快速算法有快速多极子方法( f m m ) ， 多层快速多极子方法( m l f l a ) ，基于快速傅立叶变换的自适应积分方法，f f t 法 和预校正p - f f t 法，在多层快速多极子算法中，计算复杂度仅为o ( n l o g ( n ) ) ， 所需内存可降n o ( nl o g ( n ) ) 。然后，当未知数目非常大时，m l f m a 对内存的需 求仍然较大，计算效率仍然较慢。幸运的是，并行技术的发展为计算电磁工作者 带来了新的方法和途径。在计算机硬件条件有限的情况下，并行技术是提升电磁 计算和仿真能力的重要甚至是根本手段。本文主要对并行技术在计算学中的应用 进行研究，为此，在学习、理解、消化、吸收计算电磁学领域中多层快速多极子 和基于多层快速多极子的重叠型区域分解方法的基础上，借鉴师兄师姐的工作成 果，研究了它们在并行环境中的特点，并成功将它们并行化，并应用于电大尺寸 目标电磁散射计算，给出了一定的数值算例，以验证并展示本文开发的并行算法 和解决实际问题的能力。基于上述内容本文分为五章，具体如下： 第一章：绪论。首先介绍了并行系统的发展简史：然后说明了并行系统的构 成；着重介绍了并行软件消息传递接口( m p i ) ；并简要介绍了本文的并行系统平 台；最后给出了并行算法的评价准则。 第二章：多层快速多极子原理。首先简要阐述了计算电磁学的历史和发展： 然后介绍了本文涉及到计算电磁学中矩量法的基本思想和原理：最后较详细的介 绍了快速多极子和多层快速多极子的基本思想及原理，并给出了较详细的数学描 述。 第三章：并行多层快速多极子。首先简要介绍了并行快速多极子历史和发展： 下面详细介绍了本文的并行方案；最后给出了一定的数值算例。验证了并行多层 快速多极子程序的f 确性和求解电大尺寸目标电磁散射的能力，具有较强的工程 实用性。 第四章：基于多层快速多极子的重叠型区域分解并行算法。首先引入了重叠 型区域分解的基本思想；接下来介绍了基于积分方程的重叠型区域分解迭代算法 的原理和数学描述；然后描述了重叠型区域分解迭代算法缓冲区的划分；详细描 述了基于快速多极子重叠型区域分解迭代算法的基本原理和计算复杂度分析；最 后计算了电大尺寸目标的电磁散射，并给出了一些数值算例，验证并展示了本文 并行算法对实际问题的仿真计算能力。 第五章：总结及展望。总结了本文的主要工作，浅谈了一些本文的并行开发 经验和感受，并给出了本文中可以进一步优化、研究和丌发的地方。 2 多层快速多极了捧奉原理硕l 论文 2 多层快速多极子基本原理 2 i 引言 九十年代以来，伴随着各种快速算法的出现和计算机技术的飞速发展，计算 电磁学取得了长足的进步。其中的快速多极子方法( f m m ：f a s tm u l t i p o l em e t h o d ) 【1 1 和多层快速多极子方法( m l f m a ：m u l t i l e v e lf a s tm u l t i p o l ea l g o r i t h m ) 1 2 , 3 】f 6 7 1 就 是当今积分方程研究成果的杰出代表。目前快速多极子方法和多层快速多极子方 法已经广泛应用于各种复杂目标的电磁辐射与散射分析。尤其是多层快速多极子 方法，更是成为了当今最快速的积分方程求解器的杰出代表。 快速多极子方法( f m m ) 和多层快速多极子方法( m l f m a ) 是电磁场积分方程迭 代求解的快速算法，加速了迭代过程中矩阵矢量相乘计算。对于未知量数目为 的散射问题，直接求逆的计算复杂度为0 ( n 3 ) 量级，存储量为d f 2 ) 量级；迭 代技术如共轭梯度迭代方法计算复杂度为o f 。n 2 ) 量级，。为迭代收敛所需 的迭代次数。采用f m m 求解，计算复杂度可减至d f 。，h 51 量级，存储量降至 d ( n 1 量级；采用m l f m a 求解，计算复杂度可进一步降至d ( j v 。，m o g 1 量级、 存储量降至o ( m o g n l 量级。所以f m m 与m l f m a 十分适合电大尺寸三维复杂目标 矢量电磁散射求解。作为数值方法，快速多极子方法( f m m ) 和多层快速多极子方 法( m l f m a ) 具有数值误差可控、计算精度高、通用性强和应用范围宽的优点p s - ：, o 。 相对于p 0 等高频方法，它们又具有数学公式复杂、不易编程、优化参数较多等 特点。f m m 与m l f m a 既适用于单站r c s 计算，也适用于双站r c s 计算；既可分析 凸形目标散射，又可分析凹形目标散射，适合于任意外形的三维金属目标r c s 计 算。该方法适用于任意极化( 各种线极化和圆极化) 照射条件下命属目标r c s 的 计算：既可直接计算各关键部件散射，也可用于整机散射的精确建模；既可分析 理想导体目标散射，又可分析非理想导体、介质、介质导体复合体、涂敷目标等 目标散射。对于大型复杂平台上的天线的辐射问题的分析也能很好的适用。 6 硕= t ：论文区域分解结合多层快速多极了并行技术 2 2 矩量法基础 f m m 和m l f m a 仍基于矩量法框架，为此先介绍三维目标散射的矩量法求解思 路。对于三维导体电磁散射( 时谐因子设置为e x p ( j o a t ) ) ，电场积分方程表示为 3 1 , 3 2 1 ： 肚矿1 6 ( r r 7 ) 。j ( r ) 搬= ；e 7 ( r ) ( 2 1 ) 如，) - i + 吉v v m r 卜睢v v 嵩 汜2 ， 其中，万( ，7 ) 为并矢格林函数。，7 为自由空间的波阻抗( 7 7 = 1 2 0 # ) ，e7 ( ，) 为入射场，j ( r ) 为待求电流，t 表示所分析物体表面的单位切线方向。磁场积分 方程则为： ；( 圭j ( r ) 赢v i _ i c o ( r ，r 忡归卜( 品x h ，( r ) ) ( 2 3 ) 其中，h 。( 厂) 表示入射磁场，r i 则表示外法线方向，g o ( r r ) 为自由空间的格 林函数。表达式为： g o = e x p 芴( - j k 广o r ) ( 2 4 ) 通常情况下，磁场积分方程( m f i e ) 生成的矩量法矩阵的条件数要优于电场积 分方程( e f i e ) 。但m f i e 在分析非闭合问题时不适用。并且当在分析闭合结构问 题时，它们都会碰到一个问题，会出现内谐振现象。通常e f i e 与m f i e 的谐振点 并不一样。为了避免这一问题，学者们引入混合场积分方程( c f i e ) 3 3 , 3 4 1 。在c f i e 的选取在实际中有t e n e ，n e n h ，n e t h ，及t e n h 四种类型 3 5 1 。这旱采用的是t e n h 型的混合场积分方程，因为它形成的矩阵性态好，并能真币消除内谐振现象。它 可以表示为： e f i e + ( 1 一a ) m f i e 0 口1 ( 2 5 ) 7 7 我们采用平面三角形贴片模拟目标几何表面，基函数选择为平面r w g 基函数。 它的数学表达式如下： 2 多层快速多极子幕本原理坝 ：论文 a 。( r ) = 群表示相应三角形的面积。各符号含义如下图所示。 一 杉夕 t ： 武1 ( 2 6 ) 图2 1r w g 基函数不葸图，两个公用一边的二角卑兀 对c i f e 实施伽略会方法，当然也可以采用线匹配方法。得到矩阵方程为： z ，。口。= 吃，m = l 2 ， ( 2 7 ) 其中： z 脚一= 口风螅a 埘皿( 7 + 古v v g o a 疗钌豳 + ( 1 一口互i 瓜人册。a 。劣一( 1 一口) 服a m 疗v 服g o a 一嬲铹 圪= f c k i n c + ( 1 - a ) 五x 矿p ( 2 8 ) a 刀表示基函数的扩展系数j ( r ) a a 。( r ) 。 矩量法的一个难点是自作用项奇异性以及两个离的很近的元素的近奇异性 的处理。由于选用平面r w g 基函数，磁场积分方程中的主值积分项为零。这是由 于对奇异项 坂h 而v i i s o g o a 。d s d s = 5 互s o a 晰诹皿v g o 叭d s d s ( 2 9 ) 而v g o 的方向为( r r7 ) ，它与基函数同属此三角形的切面方向，( r r ) a 。要 么为零，要么就为二的方向，所以这一项的值为零。所以奇异项主要说的是电 场积分方程( e f i e ) 部分。对于近场作用的计算，通常要将e f i e 换成混合势积 分方程( m p i e ) 来处理。因为m p i e 的奇异性要比e f i e 低一级。此时z 。中e f i e 贡献的为： 巧 巧 庀 叮 呵 舵 a： ，a： 厶一珥一珥。 硕i j 论文区域分解结合多层快速多极子并行技术 口盹( 皿a ，皿g o a 。峦访一去皿v ，一。，g o v ：。嘏体) c 2 。， 上式中，r w g 的三角形表面散度有解析表达式为 v 、a 。= 每r 在巧内 一每r 在巧内 ( 2 1 1 ) 0 其它情况 当枳分i 贝甲烬与规祭二角彤柑l j 时，一杆口j 远译阴办绣米用刀口城讨异坝采处埋返 一奇异积分。 毗 珏人i ，l ( g 一页1 + 页1 ) 八方豳一去，r 。( g 0 一页1 + 页1 形 ，毋豳) ( 2 1 2 ) 对移除了奇异项的积分的项，我们采用三角形区域的高斯积分i 来处理。 毗( ，( g o i 1 ) 峦体一i 1 。v 。a 。( g o i 1 ) v ：嬲锻) ( 2 1 3 ) 而有奇异性的项我们则采用解析计算公式1 3 7 , 3 8 1 来表示。 口纸( 瓜a 。皿去a 。脔锻一去瓜v a 。皿去v a 。布体 c 2 - 4 ， 按三角形循环来填充e f i e 近作用矩阵，在处理m f i e 近作用中的第二项积分 j l a 。磊v f 点o g o a 。d s d s ，按如下方式进行处理： 皿a 册卉皿v g o a 。搬协 代入r w g 函数，得 = c 豫( r r i ) h 媳v g o ( r - r 2 ) d s d s = c f n ( r r i ) h 瓜厂( r ，r 7 ) ( r - r ) r t _ r 2 ) 搬铹 ( 2 1 5 ) = c 服( r r 1 ) 五服巾，r ，) ( r - r ) ( r - r + r - r z ) d s a s = c 1 0 ( r r 1 ) 而服m ，r ，) ( r - r ) ( 卜r , ) d s d s = c 皿( r 一_ ) 而服厂( r ，r 7 ) ( r - r ) d s 7 ( 卜r 2 ) a s 其中r l ，r 2 表示r w g 基函数中，边所在三角形中除边的两个节点外的第三个节点 的坐标。c 表示某个与积分无关的常量，f ( r ，r ) 则表示是某个与- ，r 有关的 函数。 9 2 多层伙速多极了皋奉原理坝i ：论义 通过求解得到基函数的系数后，物体表面上的电流也就知道了。这时可以根 据下式来计算r c s 州r ) 砌工睢v v 嵩j ( r ，) 峦 使用远场条件 可得 r r i = 万i i i 鬲万= ， e 、( r ) = 业，7 工 e s ( r ) = j k q 上 r r r 7 坐竺jfr，)ds，4s r r 、 e-kreikrrj(r，)ds，4r c r 、 = 石e - f l u 业刁盯乒1v v p j ( r ，) 峦 叫刁杀弦确倘 叫刁杀孤删而 表达出远场的0 ，矽方向的分量 r c s 的定义是 仃= l i m 4 丝 一” e m c l 2 2 3 快速多极子方法 ( 2 1 6 ) 快速多极子方法的基本原理是：将散射体表面上离散得到的子散射体分组。 任意两个子散射体间的互耦根据它们所在组的位置关系而采用不同的方法计算。 当它们是相邻组时，采用直接数值计算。而当它们为非相邻组时，则采用聚合 转移配置方法计算。对于一个给定的场点组，首先将它的各个非相邻组内所有 子散射体产生的的贡献“聚合”到各自的组中心表达；再将这些组的贡献由这些组 的组中心“转移”至给定场点组的组中心表达：最后将得到的所有非相邻组的贡献 由该组中心“配置”到该组内各子散射体。对于散射体表面上的n 个子散射体， 直接计算它们的互耦时，每个子散射体都是一个散射中心即为一个单极子，共需 数值计算量为o ( n 2 ) ；而应用这种快速多极子方法，任意两个子散射体的互耦由 j o 1l一叫ij v v v v 。一旷一旷 + 一i i i_l i_l 硕：f ：论文区域分解结合多层快速多极了并行技术 它们所在组的组中心联系。各个组中心就是一个多极子，其数值计算量只为 o ( n 1 5 1 7 j s 】。对于源点组来说，该组中心代表了组内所有子散射体在其非相邻 组产生的贡献：对场点组来说，该组中一f l , 代表了来自该组的所有非相邻组的贡献， 从而减少了散射中心的数目 1 3 1 ( 如图2 2 所示) 。 图2 2 将两元素的直接作用分解成二部分：聚合、转移、配置 对于e f i e 部分的并矢格林函数 氓州i + 古v v j 型l - r o l 可以写出其在角谱空间表达式 g ( r m ，r n ) = 等剪以( i 塥) p 小( j 吲稀石) 而m f i e 邵分利用恒等式，v ( 口b ) = a v b + v a b 。则有 磊v f i g o j ( ，) a s = 二i l ，v g o j ( ，娜 可以表示为 一石k zw 1 ( - j k - r m p 口胛( ；朋，茏) 磊螅j ( r 弦小。搬留2 后 而 。k 磊v i 【g o a 。d s d s 则可表示为 一砺k 2 西螅a m e - j k r m e 搬a 朋( 朋蓐) 。螅荔蓐a n e - j k r q , , 搬留2 尼 利用恒等式a ( b c ) = b ( c a ) = c ( a b ) ，则得 等弭i o 磊xa m e - 2 k 峦口胛( ；朋) l o 乏xa e 叫k 啊嬲留2 七 再用一次a ( b c ) = b ( c a ) = c ( axb ) ，表示式如下 ( 2 1 7 ) ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) ( 2 2 1 ) ( 2 2 2 ) ( 2 2 3 ) 2 多层快速多极了壮奉原理硕i j 论文 一石k2 辑皿乏n x a , , e - s t r ”嬲口舶( ；朋。珏f 。a 。e 讪豳臼2 j | ( 2 2 4 ) 其中，为转移因子，代表远区组间组中心的转换作用。孵d 2 石是谱空间单位 球面上的二重积分，积分点数为琏= 2 c ，这时在0 方向采用l 点的一维高斯 积分，矽方向采用2 l 长度的梯形法则积分。 将并矢格林函数及磁场积分的格林函数的处理表达式代入积分方程( 2 7 ) 和 ( 2 8 ) ，得到矩阵矢量相乘的f m m 表达： 乙。= z m a + 银叩( ) f m ( k ，；冈) l 。( 碱d 2 j ( 2 2 5 ) z ：z n 。r 牟z f o r 其中 r 叩( 址舻k 一槲”口) k x n x a , p ( 2 2 6 ) ( 盂) = i l 。e - y k r q ”( i 一时a 。d s 吖k ，) = ( 篆) 2 妻( 瑚2 f + l 燃琢拼阿) ( 2 2 7 ) 其中屏代表来自附近组的贡献。r 。，( j i ) ，f q 。( 七) 分别为聚合因子、配置因子。由 于e = 0 ，即f n , q - 与o ，矽有关，与r 无关，并且它与远场的计算有类似的地方。 所以e 又被称为辐射方向图，r 。则被称为接收方向图。 ( a )( b ) 图2 3 ( a ) u 个未知量直接相互耦合“链接”数是鼍级( b ) “交换机”的引入减少了电流单 元间直接的耦合“链接”数 由于远区场源耦合通过各自组中心实现，待计算的子散射体中心得到减 少，所以f m m 加速了矩阵矢量相乘计算，计算机存储量也大大降低了。对于f m m ， 其计算量、存储量为o ( n | 5j 量级。快速多级子技术中的组不能太大，因为那样 转移过程虽然能有效地计算，但是聚合和发散的过程都不能有效的进行，组也不 能太小，因为那样聚合和发散的过程虽然能有效的进行，然而转移的过程又不能 1 2 硕_ 上论文i 苎：域分解结合多层快速多极了并行技术 有效的计算。所以我们通过选择恰当组的大小来获得快速多级子的最佳效率。 2 4 多层快速多极子方法 对于电大尺寸目标的散射，其未知量数目n 1 ，此时应用多层快速多 极子方法( m l f m a ) 将获得比快速多极子方法更高的效率。多层快速多极子方法 是快速多极子方法在多层级结构( h i e r a c h i c a ll ys t r u c t u r e ) 中的推广。对于 n 体互耦，多层快速多极子方法采用多层分区计算f i 一 1 6 3 1 。即对于附近区强耦合 量直接计算；对于非附近区耦合量则用多层快速多极子方法实现。多层快速多极 子方法基于树形结构计算，其特点是：逐层聚合、逐层转移、逐层配置、嵌套递 推。对于二维情况，它将求解区域用一正方形包围，然后再细分为4 个子正方形， 该层记为第一层。将每个子正方形再细分为4 个更小的子正方形，则得到第二层， 此时共有4 2 个f 方形。依次类推得到更高层。对于三维情况，则用一正方体包 围，第一层得到8 个子正方体。随着层数增加，每个子正方体再细分为8 个更小 的子正方体。显然，对于二维，三维情况，第f 层子正方形和子f 方体的数目分 别为4 ，8 ，。这种分层级结构如图2 4 所示。对于散射问题，最高层的每个正方 形或j 下方体的边长为半个波长：左右，由此可以确定求解一个给定尺寸的目标散射 时多层快速多极子方法所需的层数p l 。 层父层 子甚 图2 4 二维多层快速多极子方法中的分层级结构 由于每层数值汁算量均为p ( ) 量级，共有，馏v 层，所以多层快速多极子方 法计算矩阵与矢量相乘的工作量为o ( n l o g n ) 量级。内存需求也为o ( n l o g n ) 量 级。 基于图2 4 的分层级结构，多层快速多极子方法由上行过程、下行过程两部 分组成。上行过程分为最高层的多极展丌( m e x p ) 、子层到父层的多极聚合( m m ) 。 2 多层快速多极了筚奉原理 钡i j 论文 上行过程在多极聚合到第二层后，经远亲转移计算转向下行过程。下行过程则分 为父层到子层的多极配置( l l ) 、同层问远亲组的转移( m l ) 和最高层的部分场展丌 ( l e x p ) 。 多层快速多极子方法求解式的具体步骤分为1 3 1 ： ( 1 ) 最高层的多极展丌( m e x p - - m u l t i p o l ee x p a n s i o n ) ：计算公式同于快速多 极子方法中聚合量的计算，为 s 。，瞎) = 吃，忙声，( 2 2 8 ) v s m i 忙) ：上凼, e i k r l m 防一埘，r m , ) ( 2 2 9 ) 其中，m 为最高层中，子散射体f 所在组的组中心。s 。舡) 、，隹) 分别为 最高层m7 组的聚合量，聚合因子。 ( 2 ) 多极聚合( m m - - m u l ti p o l ee x p a n s i o nt om u l t i p o l ee x p a n s i o n ) ：是将 源子散射体在子层子组中心的聚合量平移到父层父组中心表达。 乩m ，) ：p ，k i ，g ，。) 月= i ( 2 3 0 ) 其中，所；，m j 分别为第，层，第，一l 层中源子散射体f 所在组的组中心，埘：， ，卅；。分别为m ；，历；一。的矢径。注意：插值矩阵，玎为稀疏矩阵。 ( 3 ) 多极转移( m l m u l t i p o l ee x p a n s i o nt ol o c a le x p a n s i o n ) ：多极聚合 到第二层后，便不再向上聚合。此时开始多极转移，即将源区的外向波转移为场 区的内向波，为下行过程做准备。 在第二层，在源区组中心聊的聚合量s 。：f 七l 即为以聊为中心的外向波，以 、， 、 场区组中心m 为中心的内向波b m ，忙j 如下计算： b m 2 ( c ) ：口r a m g 声加；g ) m m 的远亲 ( 2 3 1 ) 口。朋，( 名j ；) = i t ( 2 1 + 1 ) h e 。( 饥。，) 另( 名。，j ) ( 2 3 2 ) i = 0 其中，口删怔j 为第二层上的转移因子。 ( 4 ) 多极配置( l l l o c a le x p a n s i o nt ol o c a le x p a n s i o n ) ：是将在以父层 父组中心为中心的内向波转化为以子层子组中心为中心的内向波表达。多极配置 是多极聚合的逆过程。与多极聚合中子层到父层采用内插计算类似，多极配置过 程中，父层到子层则采用伴随内插计算。 对于在第，一l 层，组中心为m f - 1 的组内场点，而言，来自于该组所有非附近 组的贡献为： 1 4 硕l ：论义 区域分解结合多层伙速多极了并行技术 ，= p2 y 帅忙) b c c ) ( 2 3 3 ) 离散求积分，得 ，：k i - i ，h ，一。加，k h 一。如，) ( 2 3 4 ) ，= ，砌h ，晖( ，一i 加，j j 9 0 h 惦( ，一i 如，) ( 2 丹= i 将父层父组的非附近组贡献平移到子层子组的组中心表达为： ，：羔w 厅i j ( c ，一净旦? ( c ，玎) ( 2 3 5 ) n = l b 圳g ，。) ：k i i ，。p 睹t ，一m 小- b g ( 川矽h 。，w 。 ( 2 3 6 ) ( 5 ) 多极转移( m l - - m u l t i p o l ee x p a n s i o nt ol o c a le x p a n s i o n ) ：为了继续 从父层到子层递推下去，就必须得到来自于子层子组的所有非附近组的贡献。在 多极配置过程中，已经考虑了父层父组的所有非附近组的贡献，尚未考虑的是该 子层子组的远亲组贡献。于是，在多极配置的基础上再叠加上子层子组的远亲贡 献，就得到了子层子组的所有非附近组的贡献。计算式如下： 占2 ，皓。) =口。，g 声，；瞎，。)