06_2多层快速多极子技术MLFMM.ppt

FEKO Suite 5.5基本算法介绍 快速多极子（FMM） 多层快速多极子技术（MLFMM） FMA overview 我们知道解线性方程组的方法可分为两类：一类是直接法，如高斯消元法等；一类是迭代法，如：共轭梯度法等 用矩量法（MoM）求解线性方程组，它的系数矩阵是满秩的。如用直接法求解，则计算机内存需要O（N2），运算量达O（N3）；如用迭代法求解，内存一样需要O（N2），而每次迭代的运算量达O(N2)).如此之多的内存需要量，如此之大的运算量，大大限制了矩量法的应用范围，在90年代以前，矩量法仅仅适用于电小尺寸物体（物理尺寸/工作波长 10）。 20世纪90年代以后，情况发生了改变，目前矩量法已可以计算相当大的电大尺寸物体，这主要归归功于Rokhlin提出的快速多极子算法，这是一种减少内存需求，加快矩阵和矢量相乘的技术。 快速多极子技术的基本思路 大家都知道，迭代法的运算量主要取决于矩阵与矢量相乘的运算量。从物理意义上看，矩阵与矢量相乘虽实际上是源点对场点的作用，然由于整个考虑的源点和场点是重合的，因此也可以形式地认为是等效电流之间的相互作用。 快速多极子技术的基本思路是首先将未知等效电流分成小组。分小组可以按如下方式进行：首先用一个适当大小的长方体将物体刚好包住，然后将此长方体分成小长方体（小长方体究竟多大合适，下面再作具体分析），并将非空小长方体标出储存。此处非空小长方体是指其内有未知等效电流的小长方体，也就是被物体边界相割的小长方体。对任何一个非空小长方体，其他的非空小长方体可以分成两类：一类为近相互作用，一类是远相互作用。通常，两小长方体中心之间的距离小于半个波长的为近相互作用，否则为远相互作用。 近远相互作用介绍 下边来分析两小长方体A和B的远相互作用。设A和B内分别都有100个未知数，如图1所示。如果用通常方式来执行他们之间的相互作用，则需要100*100次计算机操作。而快速多极子技术是用一种新的方式来执行A和B之间的远相互作用。其基本思路是将整个相互作用过程分解成三步：聚集、转移、发散。聚集就是将分布在A内的100个未知数所对应的等效电流聚集在A的中心。其目的是获得一组具有下列转移特性的新函数：A内所有等效电流对远处的作用可以由执行这组函数的转移完成；转移就是将聚集过程中得到的一组函数由A的中心转移到B的中心；发散就是将转移到B中心的那组函数发散到B内所有100个未知数所对应的等效电流上，从而完成A和B的远相互作用。此种作用方式由图2表示。下边会阐述平面波函数具有上述转移特性，而且在能够保证高精度情况下，所需平面波个数少于原未知数个数。这就是说，完成新函数从A中心到B中心的转移，只需要少于100次的计算机操作。这就是快速多极子技术能够加快完成A和B远相互作用的原因。作用过程的分解来源于积分方程中格林函数的多极子展开，故此项技术称为快速多极子技术。由于格林函数的多极子展开在近相互作用时很难达到满意精度，则这种新作用方式只适用于远相互作用。这也就是我们将相互作用分成近相互作用和远相互作用的原因。 远相互作用示意图 远相互作用FMM实施方法 小长方体多大合适 这里我们讨论小长方体多大合适的问题？ 由上述分析可以知道：转移步骤所需计算量很小。然而，聚集和发散步骤并非如此。实际上，将原来的100个未知数所对应的100个基函数聚集成大致100个平面波函数，需要100x100次计算机操作；将100个平面波函数发散给100个未知数所对应的100个基函数，也需要100x100次计算机操作。因此，如果只考虑两个小长方体的远相互作用，快速多极子技术所需计算量是超过通常方式的计算量。然而，当我们考虑100个小长方体的远相互作用时，情况就不同了。此时有100x100=10000个未知数，用通常方式完成它们的相互作用需10000x10000次计算机操作。如用快速多极子技术，每个小长方体中的聚集需100x100次计算机操作，现有100个小长方体，因此整个聚集需100x100x100次计算机操作。同样道理，整个发散需100x100x100次计算机操作。至于转移步骤，因为完成一次转移需100次计算机操作，现有100个小长方体，需100x100次转移，因此整个转移也需100x100x100次计算机操作，故用快速多极子技术完成整个相互作用需3*100x100x100次计算机操作，大大少于通常方式的计算量。由此可见，小长方体尺寸不能过大，因为过大会导致聚集和发散两步骤地计算量过大；小长方体尺寸不能过小，因为过小会导致转移步骤的计算量过大。严格来说，假如有N个未知量，分成M组，这样每组大致有N/M个未知数。根据上面分析，聚集和发散步骤所需计算机操作都是O（N2/M），转移步骤需O（NM）次计算机操作。因此完成整个相互作用需要O（N