（信号与信息处理专业论文）并行计算在电磁学中的几个应用.pdf

硕 : 论文并行计算在电 磁学中的几个应用 ab s t r 8 c t withthe d e v e l o p m ent o f hi gh一 p e ri b rmancep ct e c h 币 q ue， p aj 渔 1 1 elcom p u t in g 幼d e l y e l e c t r o used i n m a n y 6 e l ds o fc o m p u t ing，e n gi n e e ri n gt echno l o gy m agn e t i c s . thep re s ent m etho d so fcompu ta t i 0 nel e c trom a g ” 比c sal l strongl yre l yo nthe avai l ablecom p u t e r re sou r c e . withth e e l e c tric s i zeo f th e prob l em we s h o ul d so l vebec 0 m e large r and l arger ， th e s p e e d and m emo ryo f the com p u t e r c ann o t s 对 1 5 斤the needin g o f scienc e a n d t e c hoo l o gy p 即 旧 】 1 e l com p u t i ngi s the ri ght m e th 0 d fo r usi n g c o m p u t e r 比 so uree e ffect i v e l y . t h e th e s ism a i 川 y r e v l e w edso m e works i hav e doneinth e p ast 幻 丹 o years. i di d some re se ar c b esinse v e r a 】 即p l l c at i ons o f p 越 al 】 elcom p u t in g . ma y bethese加t al l bele n g to伽 e l e c tl . m a gnetic s d o r n a ll l ai the b e gi 川 i n go f the th e si s ， 罗 n e ti c al gori t 】1 1 nandh o wtop ar a l l e l i t havebee n 访 t r o d u 以 劝and a p ar a l l e i g enet i al g o ri t h mtoc al c ul ate the 丘 e q u ency se l e c ti v i tysu ri 五 c e ( f s s ) i s p r o gr a rt u n ed. s eco 喊 the arti c l e rese areh edthe app l l c 越 i o n o f p ar a 】 l e l com p utin g i n m u l ti l e v e l fa s t m ul ti poleal g o n t h l l l( ml f m a ) .were ai l 及 月 坛 p ar al l e lm u lti l eve lfi 巧 tmuh ip o l e al g o ri t 肠 m(ml f m a ) .we c al culat ed耐ars c a tt e ri n g c ro s s 一 s e c t l o n恨c s ) o f a con d u ctor s p h e rewithz ，4 0 0 ， 0 0 0 u 点 幻 1 o wns tos h o wt 1 1 a t we hav e the abi l i tytoso i v e th e b i g u n ki 1 o wn q uan t i typ r o b l e m . f ir 以 1 1 y ， ap ar a 1 1 e l ove r l appedd o m a 1 nd eco m pos i ti on meth o dfor m u 1 t 1 1 eve l n 比 t m u l t i p o l e(p ar al l e lle一 o d d m ml f m a )b a sh 沈 nd e v e l o ped .wecalc ul at ed r a 山 叮 ， 泊 讹行 n g cros s 一 s e ct i o n扭c s ) o f a con d u c to r s p h e re初thl ，7 0 0 刀 0 0 也 止 n o 叭 尾 isb y usin g 止 e p ar al l e l l bo d d m一 ml f ma. k e y wo r d s : c o m p u tati o n al e l e c t r o m a g n e t i c s ， gen etica l g o ri t h m ，几 s tmul t i p o le d o m ai n d e c o m p o s iti on m e t h o d ， m p i p a r a 】 l e lc o m p u t i ng， al g o ri t 加 m ，o v e ri a p p ed 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均己在论文 中作了明确的说明。 研究生签名:年月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电 子和纸质文档，可以借阅 载 上网公布本学位论文的部分或全部内容，可以向 有关部门 或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名:年月日 硕 十 论文并行计算在电 磁学中的几个应用 ， 引言 随着计算机的应用日 趋复杂， 从数据处理， 信息处理，知识处理到智能处理， 应 用范围越来越广， 处理问题的规模越来越大， 因此对计算机的运算速度和处理能力要 求也越来越高。 尤其是一些具有挑战意义的科学工程计算问题， 如目 前的计算电 磁学 方法都强烈地依赖于可以利用的计算机资源。 随着所需解决问题的电尺寸的增大， 单 个计算机的速度和内存都远远不能满足科学技术和工程问题的需求。 尽管现在的计算机比十年前快了 一百倍， 但是计算机科学家和工程师还需要更快 的速度。 他们己 经对问题进行了大量的简化， 但是现在的计算机仍然需要数小时， 数 日甚至数周来完成他们的程序。 可以 预见， 当你的计算机运行程序时， 速度突然快了 10倍， 可以利用的内 存也提高了10倍， 过去一些无法忍受的计算任务将变得可以接 受。 当 然， 你可以等待计算机的c p u运行的更快，根据摩尔定律，5 年后的c pu 将 比 现在快10倍，但是对计算机速度与性能的迫切需要使人们无法忍受如此漫长的 等 待。 而并行计算技术正是高效利用计算机资源， 提高计算机速度的一种有效方法， 它 是把一个任务分配给并行计算机系统中的多个处理器， 每一个处理器只需工作在问题 的一部分， 以多个处理器的联合快速的模拟一个大问题。 因为每一个处理器的工作并 不是完全独立的， 所以各个部分之间的信息交换及交换信息量的大小是由物理模型和 所解决问题本身特性决定的。 并行计算机组使解决大规模数 值计算问 题成为可能， 并被认为是科学家和工程师 用来解决各种领域的问题的标准方法。 网络并行计算是近几年国际上并行计算新出现的一个重要研究方向。 也是热门 课 题: 网 络并行计算就是利用互联网 上的计算机资源实现所需问 题的计算。 这种并行计 算环境的显著优点是投资少. 见效快. 灵活性强等。由于科学计算的要求。 越来越多 的用户希望能具有并行计算的环境. 但是除了少数计算机用户外， 很多用户由 于资金 的不足而不能使用并行计算机. 一旦实 现网 络并行计算， 就可以 通过网 络实现超级计 算的目的，因此，就不必购买昂贵的并行计算机。 目 前， 国内 一般的 应用单位都具有局域网 或广域网。 所以 基本上具备网络计算硬 件环境。 其次.网络并行计算的系统软件 n 印 1 是当前国际上公认的一种消息传递标 准软件系统。 有了它， 就可以 在不具备并行机的情况下进行并行计算、由于该软件是 免费软件， 没有版权问题， 可以从国际互联网上获取其代码及其相应的辅助工具程序， 这无疑是对我们程序设计带来方便。 硕 卜 论文并行计算在电磁学中的几个应用 1 井行计算简介 并行计算，简单的讲， 就是用并行计算机组解决大规模数值计算问题. 本章主要 讲述并行计算的一些基本概念和系统构成。 ， . ，并行系统构成 在一个并行处理系统中， 应该包含三个部分: 并行机系统结构、并行软件和并行 算法。 当一台并行机己 经提供， 软件已 经基本配置好的情况下， 如何充分发挥并行效 率， 并行算法是一个决定性的因素。 并行算法的好坏直接关系到并行系统的使用效率。 所谓并行算法是指解题方法的精确描述， 它包括一组有穷的规则， 这些规则规定了 解 决某一特殊问题的一系列运算。 并行算法要能在所选用的并行系统上求解问 题和处理 数据。 其形式是一些可同时执行的进程的集合. 这些进程相互作用和协调工作， 实现 对给定问题的求解。 不论采用何种途径实现并行算法， 都有一些基本的公共因素必须考虑。 ( 1) 洞察 并提取并行性: 当针对一个具体问题设计并行算法时， 如果求解该问 题的串行算法己 知， 则就以 这个串 行算法为分析的出发点。 如果该串行算法中没有明显的并行性， 则 应当利用已有的相关知识提取其内在的并行性。 (2) 必须考虑通信开销: 在决定并行 算法复杂性时， 必须考虑通信开销。 这是因为有时 通信复杂性比计算复杂性还高。 换 句话说， 处理机之间数据的调度、 传输所花的时间比实际计算时间还多。 这就需要在 设计时尽量采取简单的通讯方式， 并使传输的数据量尽可能小， 而在分析并行性能时 也不能忽视通信的开销。 (3) 并行算法必须适合于所选用的并行系统: 并行算法直接 依赖于并行处理系统， 不同 类型系统上的并行算法有很大的区别。 在开发时必须注意 这一点。 并行算法可以用很多标准来评价， 但通常人们最关心的是算法与它能求解的问 题 的规模之间的关系。为此，对并行算法性能的评价通常采用以下基本参数:加速比、 效率、成本以及算法复杂性。 1并行算法加速比:算法在单处理机上的实际执行时间与使用 p台处理 机时算法的实际执行时间之比。 2并行算法的效率:最快的串行算法在单处理机上的实际执行时间与使 用p 台处理机时算法的实际执行时间之比。 3 并行算法的成本:并行算法运行时间和算法所用机器台数的乘积。 4 并行算法复杂性: 求解规模为n 的问 题所花费的运行时间t ( n)。 当n 趋近于无 穷大时，时间复杂性的极限 称为算法的渐进时间复杂性。 硕 1 : 论文并行计算在电 磁学中的几个应用 理想情况下加速比 等于并行计算机的台数p ， 但由 于算法并行度不高以及通讯和 同 步等时间 的开销， 加速比 是不 可 能 达到p 的. 研究并 行算法的目 的 就在于提高 算法 的加速比，降低时间复杂性。 对于本论题来说，并行系统为 一组以 太网络连接的高性能的p c机群，所有 p c 机的操作系统为micro so丘 win d o w s x p ， 在 并 行 计 算系 统中 ， 一 个 可 移 植的 、 基于 消 息 传递的 并 行 编 程平台 是 必 不可 少的 消息传递编程是一种显式编程，大多数系统使用发送和接收函数来交换数据。目 前， 在分布存储并行编程环境下已经存在许多通用且成熟的消息传递软件包，其中 m p i ( m e s s 叱 e p as s i n g l nter 几 c e ) 和p v m( p ar a l le l vi 由 ja l m ac h ine) 是 应用比 较广泛的 两 种.基于m p i 可以 提供一个实用的、可移植的、高效灵活的接口 库，所以在本论题 中，选用mp i 做为并行开发的软件平台。 1 . z m p i 简介 mp i 是由研究实验室、 大学和产业界联合研制的一个消息传递的标准。 m p i 环境 包括一个 m p i函数库，提供了上百个函数。在消息传递库方法的并行编程中，一组 进程所执行的程序是用标准串行语言书写的代码加上用于消息接收和发送的库函数 的调用。在绝大部分 mp i 实现中，一组固定进程在程序初始化的时候生成，一个处 理器生成一个进程， 这些进程可以 执行相同或不同的代码。 进程间的通信可以是点对 点的， 也可以是群集的。目 前， 除了商业版本以 外， 在很多网站上都可以下载到m p i 的多个由国际上一些研究团体开发的免费版本。 m p i 是一个库而不是一门语言。许多人认为mp i 就是一种并行语言这是不准确 的， 但是按照并行语言的分类可以 把f o r t r a n + m pi或 c 十 mpi 看作是一种在原来 串 行 语 言 基 础 之 上 扩 展 后 得 到 的 井 行 语 言 m p i 库 可 以 被 f o 义 印 决 n 7 7/ c 用 。 找 n 川 9 0 / c 什调用。从语法上说它遵守所有对库函数/ 过程的调用规 则和一般的函数/ 过程没有什么区别。 h n 钾 1 是一种消息传递编程模型并成为这种编程模型的代表和事实上的标准。mp i 虽然很庞大但是它的最终目的是服务于进程间通信这一目 标的。 消息传递方式是广泛应用于多类并行机的一种模式. 特别是那些分布存储并行机 尽管在具体的实现上有许多不同 ， 但通过消息完成进程通信的基本概念是容易理解 的 十多年来这种模式在重要的 计算应用中己 取得了实质进步。 有效和可移植地实现一 个消息传递系统是可行的。 因此通过定义核心库程序的语法语义， 这将在大范围计算 机上可有效实现，将有益于广大用户.这是mp i 产生的重要原因. 硕 : 论文并行计算在电磁学中的几个应用 ， . 3本课题的井行平台及评价井行效率的标准 ， . 3 . ， 并行平台 硬件方面: 教研室根据需求搭建了两个高性能高效率的并行计算机平台， 一个是 由十八台适合数值算法研究的高性价比的计算机 ( p e n t l um w 2. s g ，i g 内存， m ic m so ft 钻n d o wsxp 操作系统) 组成， 并选用传输速率为100/1000m b s 的千兆以 太 网络组成处理机群， 具有良 好的可复用性和可扩展性， 非常适用于网络并行计算方法 的研究. 另一个是根据更大规模未知量计算的需求， 由 十几台最新配置计算机组成的 更为高效的计算平台。( pentium w 双核1 . s g ， z g内存， 珑croso ftv 八 1 1 d o w s xp 操 作系统，千兆以 太网) ，完全可以 满足大未知量计算的需求。 软件方面，我们选用国内外较为流行的 m pic hz 版本的并行软件与 f o r t r a n 语言相结合进行并行程序设计， 它具有通用性强， 系统规模小， 成熟度高，可以免费 获得等优点，非常适合于数值计算。 ， . 3. 2 井行效率的评价 并行计算主要是为了解决串行程序计算速度或内存不足而设计的。因此对并行 效率的评价也因该根据实际需要从程序执行时间和单机内存的减少来判断。 加速比定义为 凡 串行算法在处理机的执行时间 并行算法在具体有p 台处理机的系统上的执行时间 并行算法效率定义为 e ; = 凡/ p 硕士论文 并行计算在电磁学中的几个应用 2 并行遗传算法 遗传算法是模拟生物进化过程的计算模型. 它是自然遗传学和计算机科学相互结 合渗透而形成的新的计算方法。 生物的进化过程主要是通过染色体之间的交叉和变异 来完成的。本章简要介绍了遗传算法的概念及对其并行的流程和效率比较。 2.1遗传算法 遗 传 算 法 是 从 代 表问 题 可 能 潜 在 解 集 的 一 个 种 群 开 始的 ， 而 一 个 种 群 则由 经 过 基 因编码的一定数目的个体组成。 每个个体实际上是染色体带有特征的实体。 染色体作 为 遗传物质的主要载体. 即多个基因的 集合， 其内 部表现( 即 基因型) 是某种基因组合， 它决定了个体的形状的外部表现， 如黑头发的特征是由染色体中控制这一特征的某种 基因组合决定的。 因此， 在一开始需要实现从表现型到基因型的映射即编码工作。由 于仿照基因编码的工作很复杂， 我们往往进行简化， 如二进制编码。 初代种群产生之 后，按照适者生存和优胜劣汰的原理，逐代演化产生越来越好的近似解。在每一代， 根据问题域中个体的适应度大小挑选个体， 并借助于自 然遗传学的遗传算子进行组合 交叉和变异， 产生出代表新的解集的种群。 这个过程将导致种群像自 然进化一样的后 生代种群比前代更加适应于环境， 末代种群中的最优个体经过解码， 可以作为问 题近 似最优解。 在 遗 传 算 法 中 。将 维 决 策 向 量 用 、 一 。 ，二 ，二 、 r 用 个 记 ” 、 1= ，2 ， 所组成的符号串用 x 来表示: = 戈 如 = xl， xz，.刘r 把 每 一 个戈， (i月， 2 ) ， 看 作 一 个 遗 传 基 因 。 它 的 所 有 可 能 取 值 称 为 等 位 基 因 。 这样.x 就可看作是由n 个遗传基因所组成的一个染色体( 或个体) 。对于每个个体， 要按照一定的规则确定出 其适应度。 个体的适应度与其对应的 个体表现型x 的目 标函 数值相关联， x 越接近于目 标函数的最优点。 其适应度越大:反之适应度越小。所有 染色体x 就组成了问题的搜索空间。 生物的进化是以集团为主体的. 与此对应. 遗传算法的运算对象是由m 个个体所 组成的 集合. 称为群体。 与生物一代一代的自 然进化过程类似. 遗传算法的运算过程 也是一个反复迭代过程， 第t 代群体记为p (t)， 经过一代遗传和进化后. 得到第1 +t 代群 体， 也是由 多个个体组 成的 集 合， 记为p( t + 1) 。这个群体不断地经过遗传和进 5 硕 1 丁 论文并行计算在电 磁学中的凡个应用 化操作. 并且每次都按优胜劣汰的规则将适应度较高的个体更多的遗传到下一代. 这 样最终在群体中将会得到一个优良的个体x 。 它达到或接近于问题的最优解x 。 遗传算法中最优解的搜索过程也模仿生物的这种进化过程。 使用所谓的遗传算子 作用于 群体中， 进行下述的 遗传 操作. 从而得到 新 一 代群体p (t 十 1) 。主 要操作有: 1 、选择:根据各个个体的适应度，按照一定的规则或方法.从第 t代群体中选 择出 一些优良 的个体遗传到下一代群体风t +1) 中; 2 、 交叉: 将群 体p( o 内 的 各 个个 体随 机 搭 配 成 对， 对 每一 对 个体. 以 某 个概 率( 称 为交叉概率) 交换它们之间的部分染色体。 3 、 变异: 对群体p (t)中的每一 个个体.以 某 一概率( 称为变异概率 ) 改变 某一 个 或某一些基因座上的基因值为其他的等位基因。 总之，遗传算法就是一种介于随机搜索和穷举法之间的寻找某问题最优值的 算法。 2. 2井行遗传算法 遗传算法是一种求解复杂系统优化问题的有效工具， 其本身具有的固有并行性， 在并行系统构架下有着非常广阔的应用前景。 由于问题规模的不断扩大， 面对复杂程 度越来越高的搜索空间， 串行遗传算法的搜索过程将成倍的延长。 并行遗传算法将并 行计算机的高速并行性和遗传算法的天然并行性相结合。 极大的促进了 遗传算法的研 究与应用。 并行计算的目的在于加快总体计算速度， 减小单进程内存消耗.因此，如何在控 制并行算法的成本的基础上提高算法的加速比是问题的关键所在。 研究中， 在原有遗 传算法程序的基础上所作的改动是， 在适应度的计算阶段， 有主处理器将适应度的计 算分配到各个处理器上去进行， 计算完毕之后再由 主处理器收集结果。 然后有主处理 器进行选择， 交叉， 变异等操作， 并由 此产生新一代种群。 我们采用主从式并行遗传算法， 对串行程序所作的主要改动是， 在适应度的计算 阶段， 由主处理器将适应度的计算分配到各个处理器上去进行， 计算完毕之后再由 主处理器收集结果。 然后由 主处理器进行选择、 交叉、 变异等操作， 并由 此产成新一 代种群，从而完成一次循环。 遗传算法框架结构如图2 . 1 所示，主从式并行遗传算法框架结构如图2 . 2 所示。 硕 卜 论文 并行计算在电磁学中的几个应用 牢行遗传算法框架结构 主从式遗传算法框架结构 图2 . 1 串行遗传算法框架结构图2 . 2 并行遗传算法框架结构 并行程序的核心是如何协同各节点， 将任务均匀的分配到各计算结点是影响并行 程序性能的一个主要因素。 假设 种群数目 为叩opsiz ， 优化参数个数为叩aram. 适应度评估时， 程序传给评 价函数np叩512 个长度为叩arajn的向 量。计算结束后， 评价函数返回叩ops iz个适 应度。 也即并行的任务是将一个叩即siz x nparajn的二维数组分配到各处理器， 然后 从个处理器收集一个长度为npops iz的一位数组。 任务分配采用块分配， 首先计算出 每个处理器至少分配到的染色体个数 。 ， “ mpnum= npops iz / s ize 2. 3数值分析及并行效率比 较 我们用并行遗传算法分析 f s s( 频率选择性表面)函数，加入适当惩罚函数构 7 ，硕七论文 并行计算在电磁学中的几个应用 成适应度函数，采用联赛竞争选择方法，并保留最优值进行交叉，变异。每代取 8 个个体。 由于该问题消耗内存并不大， 只是遗传一代时间较长，因此， 我们只从时间的角 度分析并行效率。 算法计算机台数遗传一代的时间并行加速比 并行效率 串行遗传算法l1 1 9 1 . 5 5 并行遗传算法 27 7 3 . 5 51 . 5 40 . 7 7 并行遗传算法 43 0 7 . 7 53 . 8 70 . 9 6 并行遗传算法 81 4 8 . 5 58 . 0 01 . 0 0 表2 . 1遗传算法并行效率比较 硕 卜 论 文 并行计算在电磁学中的几个应用 3 并行快速多极子算法 九十年代以来， 伴随着各 种快速算法的出现和计算机技术的飞 速发展， 计算电 磁 学 取 得 了 长 足 的 进 步. 其中 的 快 速 多 极 子 方 法 (f m m : 丘 巧 t multi po le m ethod) 和 多 层 快 速多 极 子 方 法 (m l f m a : m ul til ev el五 巧 t m ultipo leal go ri lb jll) 就 是 当 今 积 分 方 程 研究 成果的杰出代表。 目前快速多极子方法和多层快速多极子方法己经广泛应用于各种复 杂目 标的电磁 辐射与散射分析. 尤 其是多层快速多极子方法， 更是成为了当 今最 快速 的积分方程求解器的杰出代表。 对各种复杂目标的电磁辐射与散射分析主要受限于计算机内存大小。 为了充分利 用已有的计算机资源求解大未知量问题，并行快速多极子方法得到了迅猛发展。 本章主要阐述了快速多极子的发展及并行快速多极子的原理及实现。 3 . ， 快速多极子理论 3. ， . ， 矩量法 f 翩 和 m lf以 仍基于矩量法框架，为此先介绍三维 目标散射的矩量法求解思路。 对于 三维导体电 磁散射，电 场积分 方程表示为16 : 一 豁 工 (r.r ，). 玲 佃 = e (r) ( 3 . 1 ) r，r，止 ， 一 尸 1 万 (r ， ， ，) = 1 一 决v v ， 法 (r， 尸 ) 一 1 一 去v v ， 导 二 瑞 lk 一lk 一j lr一r ( 3 . 2 ) 其 中 ， 万 (r ， r ) 为 并 矢 格 林 函 数 。 冲 为自 由 空 间 的 波阻 抗幼= 12 0 汀 ) ， 刃(r)为 入 射场，j(尸 ) 为待求电 流。 我们采用平面三角形 贴片模拟目 标几 何表面，基函数 选择为 平面r 鹤 基函数 【 1.它的数学表达式如下: 妾 p “ 军 a 。 ( r ) = ( 3 . 3 ) 硕 士 论文 井行计算在电磁学中的几个应用 考 表 示 相 应 三 角 形 的 面 积 。 各 符 号 含 义 如 下 图 所 示 。 图3 . i r w g 基函 数示意图， 两个公 用一边的 三角单 元 采用伽略金方法，得到矩阵方程为: 全 zj， ， 一 : ，派 = 1， 2 ， ， ( 3 . 4 ) 扮一 豁 川; ， 一 扒j，v ， (r，r ，) “ ( 3 . 5 ) k 一 叉 f).砂(r) ( 3 . 6 ) 对于未知量数目为 n的散射问题，由于直接求逆方法与传统迭代技术分别需要 o(矿) 与 o(从 ler 矿) 量 级 的 计 算 复 杂 度 ， 因 此 不 适 合 求 解 电 大 尺 寸 三 维 散 射问 题 。 对 此，可采用 f 姗 与mlf m a实现高效求解.作为积分方程稀疏化的一种高效方法，f 翩 与m l f ma 不但大大加速了迭代过程中矩阵与矢量相乘计算， 并并且也大大降低了存储 量 。 快 速多 极 子 方 法的 数 学 基 础 是 矢 量 加 法 定 理 121 。 即 利 用 加 法定 理 对积 分 方 程 中 的 格林函 数进行处理. 通过在角 谱空间 中展开， 利用 平面波进行算子对角化， 最终 将密 集阵与矢量的 相乘计 算转化为 几个稀疏阵与该矢量的 相乘计算. 3. 1 . 2 快速多 极子方法基本原理 快速多极子方法的基本原理是: 将散射体表面上离散得到的子散射体分组。任 意两个子散射体间的互祸根据它们 所在组的 位置 关系而 采用不同的方法计算。 当 它们 是相邻组时， 采用直接数值计算。 而当 它们为非相邻组时， 则采用聚合一 转移一 配置方 法计算。 对于一 个给定的场点组， 首先 将它的 各个非相 邻组内 所有子散射体产生的的 贡献 “ 聚合” 到各自 的组中 心表达; 再将这些组的 贡献由 这些组的组中 心 “ 转移” 至 给定场点组的组中心表达; 最后将得到的所有非相邻组的贡献 由该组中心 “ 配置” 到 该组内各子散射体。 对于散射体表面上的n 个子散射体，直接计算它们的互祸时， 每 l 0 硕 十论 文 井行计算在电磁学中的几个应用 个 子 散 射 体 都 是 一 个 散 射 中 心 即 为 一 个 单 极 子 ， 共 需 数 值 计 算 量 为 口 伽 ， ) ; 而 应 用 这 种快速多极子方法， 任意两个子散射体的互祸由它们所在组的组中心联系。 各个组中 心 就 是 一 个 多 极 子 ， 其 数 值 计 算 量 只 为 口 扭 比 ) 【8 . 对 于 源 点 组 来 说 ， 该 组 中 心 代 表 了 组内 所有子散射体 在其非相邻组 产生的 贡献; 对场点 组来说， 该组中心 代表了 来自 该组的所有非相邻组的贡献，从而大大减少了散射中心的数目( 如图3 . 2 所示) 。 耳 图3 . 2 三维导电目 标散射的 快速多 极子分析:虚线框表示分组。 i， j 为子散射体， 耐， m 分别为 各自 的 组中 心 由加 法定理， 标量 格林函数可以 展开为阁 一 ik 全 (-l y 伪 十 l)j ，伽 冲伽 卜 (a. 习 ，d e 法 ，一 。 ， 卜所 以 有 一 尝 夕 护 标 一 )am 。 奋 二 ) ( 3 . 1 3 ) 、 。 ，(; 二 、 ) = 全 ，( 2， + 1)nl( 】，(、 . )二 (; 。 、 ) ( 3 . 1 4 ) 对于并矢格林函数 r。， 州叭 一 司 二、1 ;1。， l e 七l rj， 叽) =1 1 一下牙 vv 亡一了 万 l凡j i七一 叽 ( 3 . 1 5 ) 最终得到其在角谱空间表达 g(rj ， r，) ikr . ， 户二 =1叮一 尤( 1一 4 兀 j ) e 扭 成 ， 一 ， )a . ，( 气 ， ， 其中，a 二为转换因子，代表远区组间 组中心 的转换作用。介 关 ( 3 . 1 6 ) 是谱空间单位 球面 上的 二 重 积分 ， 积 分 点 数 为k 乙 = 2 尸， 的最大尺寸。 将并矢格林函数表达代入积分方程， 多极子模式数l二掩 刀，d为子散射体组 得到矩阵矢量相乘的 f m 材 表达: 客 胡 = 点 ，裂 协 釜 娜、 (i)x 艺蠕 ! 司 厦 编 (i)a， ， 吼 ( 3 . 1 7 ) 其中n g( n e ar g r o u p ) 代表来自 附 近组的 贡献， fg ( f a rg r o u p ) 代表来自 远 组 即 非 附 近 组 的 贡 献 。 呱 ， (i)， 呱(f) 分 别 为 聚 合 因 子 、 配 置 因 子 ， * 表 示 共 扼 运 算。 具体表达如下: 一kk 一 哀 必 低 ) ， ， 栋) ( 3 . 1 8 ) ( 3 . 1 9 ) 卜“卜“l 呱 、 (f) 一 工 产 珠认 ) 一 上 e 乍 由 于远区场源祸合通过各自 组中 心实 现， 待计算的 子散射体 中心大大 减少， 所以 f 阴 大大加 速了矩阵矢量相乘计算，计算机存储量也大大降低了，简单图示如下图 3 . 3 。 对于f 川，其计算 量、 存储量为0 (n 卜 ) 量级. 硕 1 二 论 文 井行计算在电磁学中的几个应用 图3 ， 3 an个未知量直接相互藕合 “ 链接”数是nz 量级 图3 .3 b “ 交换机” 的引入减少了电流单 元间直接的祸合 “ 链接”数 3 . ， .3 多层快速多极子 对于电 大尺寸目 标的 散射， 其未知量 数目 n 1 ， 此时应用多 层快速多极子方法 ( m l f 做) 将获得比快速多极子方法更高的 效率。多 层快速多 极子方法是 快速多极子 方 法在多 层级结构 ( h i e r a c h i c a l l ys t r u c t u r e ) 中的推广。对于n 体互祸，多层快 速多 极子 方法采用多层分区计算12，31 。即 对于附 近区强藕合量直接计 算;对于非附 近 区祸 合量则用多层快速多极子方法实 现。 多 层快速多极子方 法基于树形结 构计算， 其 特点 是: 逐层聚合、 逐层转移、 逐层配置、 嵌套递推。 对于二 维情况， 它将求解区 域 用一 正方形包围， 然后再细分为4 个子 正方形， 该层记为 第一层。 将每个子正方形 再 细分为 4个更小的子正方形，则 得到 第二层， 此时共有4 2 个正方形。 依次类推得到 更高 层. 对于三维情况， 则 用一正 方体包围， 第一层得到8 个子正方体。 随着层数增 加， 每个子正方体再细分为8 个更小的 子正方体。 显然， 对于二维， 三维 情况，第1 层子正 方形和子正方体的 数目 分别为4 ， 。 这种分 层级结 构如图4 所示。 对于散 射 问 题， 最高 层的每个正方形或正方体的 边长为半个波长左右， 由 此可以 确定求解一 个 给定尺 寸的目 标散射时 多层快速多极子 方法所需的 层数。 硕士论文 并行计算在电磁学中的几个应用 萦j 层夕层 子屏 图3 . 4二维多层快速多极子方法中的分层级结构 由 于 每 层 数 值 计 算 量 均 为 口 扭) 量 级， 共 有1 够凡 r层 ， 所以 多 层 快 速 多 极 子 方 法 计 算 矩 阵 与 矢 量 相 乘 的 工 作 量 为 口 扭losn ) 量 级 . 内 存 需 求 也 为 口 扭i ogn ) 量 级 。 基于图3 . 4 的分层级结构， 多层快速多极子方法由上行过程、 下行过程两部分组 成。 上行过程分为最高层的多极展开( m exp ) 、 子层到父层的多极聚合( 翩) 。 上行过程 在多极聚合到第二层后， 经远亲转移计算转向下行过程。 下行过程则分为父层到子层 的多极配置( l l)、同层间远亲组的转移( m l)和最高层的部分场展开( l exp)。 多 层 快速多 极 子方法求解式 ( 17的 具 体步 骤分为 13 : ( 1 ) 最高层的多极展开( m e x p 一 m u l t i p o l e e x p a n s i o n ) : 计算公式同于快速多极子 方法中聚 合量的计算，为 凡 ，阵艺 嵘 ，体 呱 ，(f) 一 妙产 中 一 讨 ji 喇 ( 3 . 2 0 ) ( 3 . 2 1 ) 其 中 ， m ， 为 最 高 层 中 ， 子 散 射 体 ， 所 在 组 的 组 中 心 。 凡 (i) 、 呱 . (i) 分 别 为 最 高 层屏组的聚合量，聚合因子。 ( 2 )多极聚合( 朋一 m u l t i p o l e e x p ans i o n t o m u l t i p o l e e x 娜n s i o n ) :是将源子 散射体在 子层子组中心的聚合量平移到父层父组中心表达。 其中， 分别为叫 m _， 仇 一i) ，)=e与 一 一 全 、 绮 目(3 . 2 2) ， _ 1 分 别 为 第 1 层 ， 第 卜1 层 中 源 子 散 射 体 1 所 在 组 的 组 中 心 ， r.;， ; ， ， _ 。 的 矢 径。 注 意 : 插值 矩 阵叽，。 为 稀 疏 矩 阵 。 ( 3 ) 多极转移( m l 一 。 u 1 t i p o l e e x p a n s i o n t o1 o c a l e x p ans i o n) :多极聚合到第 二层后， 硕士论文井行计算在电 磁学中的几个应用 便不再向上聚合。此时开始多极转移，即将源区的外向波转移为场区的内向波， 为下行过程做准备。 ._ _ _ . 在 第 于 层 ， .在 源 区 缈。 纸 的 竺 贪 粤 气 物 匹 组 甲 腼为 甲 心 思 内 同 些阴 2 叫 卿 卜 仔 凡2 因=么气耐 妙 凡玉 四 优，e用的远亲 () 即 为 以 m 为 中 心 的 外 向 波 ， 以 。 。 。 (孺 ) 二 全 ，(二 + 1)l( ，(、): (孺 ， ) ( 3 . 2 3 ) ( 3 . 2 4 ) 其 中 ， 。 。 (i) 为 第 二 层 上 的 转 移 因 子 。 ( 4 ) 多极配置( l l 一l o c a l e x p ans i o nt ol o c a l e x p a n s i o n) :是将在以父层父组 中心为中 心的内向 波转化为以子层子组中心为中心的内向 波表达。 多极配置是多极聚合的 逆过程。 与多极聚合中子层到父层采用内插计算类似， 多极配置过程中， 父层到子层 则采用伴随内插计算。 对 于 在 第卜1 层， 组中 心 为m 卜 . 的 组内 场点j 而言， 来自 于 该 组 所 有非附 近 组的 贡献为 ， = 夕 泥 气 _， (f). 气 刁 (i) ( 3 . 2 5 ) 离散求积分，得 ， = 冕 、 ，、 :，凡 一份 风 一凡 一小 ，) ( 32 6 ) 将父层父组的非附近组贡献平移到子层子组的组中心表达为: wn 呱 ， 仇 ， 卿g ，。 ) ( 3 . 2 7 ) ki艺润 -一 衅沂 。 ) 一 艺 呱e 气 ，“ 伽一 气_. 叽 一 ，。 ，凡 ， /wn ( 3 ， 2 8 ) 月 ， . 】 ( 5 ) 多极转移( m l 一 m u l t i p o 1 ee x p ans i o nt ol o c a le x p ans i o n ) :为t继续从父 层到子层 递推下去， 就必须得到来自 于子层子组的所有非附近组的贡献。 在多极配置过程 中， 已 经考虑了父层父组的所有非附近组的贡献， 尚未考虑的是该子层子组的远亲组 贡献。 于是， 在多极配置的 基础上再叠加上子层子组的 远亲贡献， 就得到了子层子组 的所有非附近组的贡献。计算式如下: 衅帆 ， )一珍一 ，砂 .;(f， . ) . 飞 加 的远袭 氏 ， (i， ， ) 一 衅仅 。 )+ 砍 嘱 。 ) 重复(4 ) 、( 5)步骤，直到最高层为止。 ( 3 . 2 9 ) ( 3 . 3 0 ) 硕 : 论文 并行计 算在电 磁学中的几个应用 ( 6 )部分场展开( l e x p 一l o c a le x p a n s i o n ) : 对于最高 层每个非空组m， 在其组 中心进行部分场展开，得到，的所有非附近组对组内场点j 的贡献， 1 、 一 尸 龙 缅(i). 凡 (i) ( 3 . 3 1 ) 其 中 : 缅(i)为 最 高 层 的 配 置 因 子 ， 氏 ( 白 为 最 高 层 上 以 组 m 为 中 心 的 内 向 波 ， 代表了组m的所有非附近组对组拼的贡献。 ( 7)直接计算附近组的贡献，与非附近组的贡献相叠加，便得到了 所有源子散射 体对场子散射体的贡献。 在多层快速多极子方法中， 转移计算在各层远亲组间进行。 转移因子具有平移不 变 性， 所以 可 事先 计 算、 存 储 在 不同 层 级中 要 用 到 的 所 有 转 移因 子a 。 3 . ， .4 快速多极子方法复杂度分析 快速多极子中， 假设有n个未知数， 分成m组， 每组的未知数个数大致为n/ m， 聚集 和发散的步 骤的 操作为o(n ， / m) ， 转移部需 要的 复 杂的为o(n x m) ， 总的 复 杂 度为0 ( 万 ， / 材+ n 、 材) ， 不 难看出 当材= 万 0 ， 时 所 需 的 操作 最少 为。 ( 万 ， ， ) 。 快速多级子技术中的组不能太大， 因为那样转移过程虽然能有效的计算， 但是聚 合和发散的过程都不能有效的进行， 组也不能太小， 因为那样聚合和发散的过程虽然 能有效的进行， 然而转移的过程又不能有效的计算。 所以 我们通过选择恰当组的大小 来获得快速多级子的最佳效率。 和快速多级子一样多层快速多级子技术也是将矩阵矢量乘分解为聚集， 转移发散 三个步骤， 然而聚集和发散的过程是从最高层进行的， 后通过移置中心， 以及插值来 完成低层的聚集和发散，至于转移过程，则和f m m方法是完全一样的， 只是多层快 速多级子只在同一层的次相邻中心进行。 先考虑聚集过程，以第二层为例。 这层的聚集是同过将起高一层即第三层的平面 波的 中 心 先 移置， 后 插 值完 成的。 假设 在 第 三 层中 的 每 一 个小 正 方 形 有o(nlj ) 个未 知 数。 这 样 就 有材二 n / 丛个小 正 方形。 因 为 聚 集 在小 正 方 形中 心的 平面 波的 未 知 数 的 个 数丛， 从 第 三 层 中 心 到 第 二 层 中 心的 移 置 过 程 所 需 的 计 算 量 小 于凡x m= n。 同样可以分析得到其他层的移置过程也要小于n，发散过程也是类似的。计算量也 是o(n ) 量级。 再来考虑转移过程， 首先介绍次相邻中 心的概念: 是指在本层不属于相邻中 心， 但在第一层隶属的组是相邻组的那些中心. 任意中心的次相邻组中是不会超过常数 c， 此前已 经说过转移过程只在次相邻组中心之间进行， 更远处的未知数的作用已经 通 过第一 层的 发散 作用得到。 假设 在 某一 层的 小 正 方形内的 未知 数是凡， 那么 有 m= n / nj个 小 正 方 形 ， 因 为 聚 集 在 每 个 小 正 方 形 的 平 面 波 个 数 小 于 未 知 数 个 数凡， l 6 论文 并行计算在电 磁学中的几个应用 又转移只 在次相邻中 心进行。 所以 在此层中完成转移过程大致c 、 丛、 m二 c 、 n 综合以上多层快速多极子技术中的聚集， 转移， 发散， 在每一层的计算量都是n， 对于未知数为n的问 题，通常可以 分为lg n，所以整个计算量为，o(n lg n ) 。 3. 2 并行快速多极子 作为数值方法， 快速多极子方法( f 朋) 和多层快速多极子方法( mlf m 人 ) 具有数值误 差可控、 计算精度高、通用性强和应用范围宽的优点。 相对于po等高频方法，它们 又具有数学公式复杂、 不易编程、 优化参数较多等特点。 f 朋与m l f 初 人 既适用于单站 rcs 计算， 也适用于双站r cs计算; 既可分析凸形目 标散射， 又可分析凹形目 标散射， 适合于任意外形的三维金属目 标r cs计算。 该方法适用于任意极化( 各种线极化和圆 极化) 照射条件下金属目 标r cs的计算: 既可直接计算各关键部件散射， 也可用于整 机散射的精确建模: 既可分析理想导体目 标散射， 又可分析非理想导体、 介质、 介质