文档介绍：第4章 基于多极展开法的广义极小残值算法
线性方程组的求解的诸多方法中，传统的Gauss消去法或是由Gauss消去法派生的其他方法解方程所需的计算次数与方程秩N的3次方成比例，而在Arnoldi算法[67]的基础上提出的GMRES迭代算这些方法应用于三维弹性静力问题的边界元法，效果依然不够理想，反而非重启型GMRES取得了比较好的效果[69]。
而为了能使非重启型GMRES实用化，必须尽量减少迭代的次数，以减少存储量和计算量。本文采用的方法就是在经典算法的基础上引入预条件技术。对于非对称矩阵，预条件的目的就是使预条件后的矩阵的特征值的分布尽量邻近。
目前最常用的预条件技术有两类，一类是左预条件，另一类是右预条件，它们的变换式为：
左预条件
右预条件
上两式中矩阵称为预条件阵，它的选取应符合两条原则，第一要使预条件处理后的矩阵的特征值分布尽量靠近，第二就是便于求解。在边界元方程组的求解中，经常取为系数矩阵的对角元素组成的对角矩阵，称为对角预条件阵，或者取由对角线元素和次对角线元素组成的带状矩阵，称为带状预条件阵。变换后的方程组记为。
对于左预条件，，；对于右预条件，，。具体算法的实施就是在计算过程中用预条件处理后的方程组代替原方程组，再进行一定的整理。
对于第二个不足，可采用双精度存储和运算或修正的Gramm-Achmidt正交化过程。为提高所得向量组的正交性，本文采用前者使正交程度大大提高，同时加快收敛速度。为避免存储量的增加，可以只引入少量双精度计算，对及相应计算采用双精度存储，精度混合运算时先将单精度转化为双精度，再用双精度计算。
快速多极展开法(FMM)
FMM基本思想
FMM源于静电场计算，用于计算大量粒子间两两相互作用的电场解析。基本点在于将粒子按空间位置分为不同的集合，
分属于距离较近的集合及集合内的粒子间的相互作用两两直接计算；当集合相距足够远时，集合之间多个粒子的相互作用根据多极展开公式近似计算。
空间中多个粒子对某一粒子作用叠加的直接计算式为
(4-15)
式中，是一组影响系数。
(4-15)式在数学、物理、化学及生物等不同学科中表达形式相近，普遍用于化学中分子动力学和量子力学模拟、天文学中大规模引力系统的计算、电子工程中的电容和电感的计算和不可压缩液体的动力学分析[70-73]。
可见，在使用上述公式求解电荷间的相互作用问题时，当需要同时计算的电荷数增加时，计算量将以阶上升。由Greengard等提出的快速多极展开法，能够基于球谐函数在空间中的多极展开，采用递归算法结构，将多个粒子对某处的作用层层近似转化为单一粒子的作用，将计算量降为阶。直接计算如图4-1所示，当距离足够远时，使用FMM方法相当于把Q区域内的所有粒子对位于P点的粒子的作用近似归结为域内某一点对P点粒子的作用，如图4-2所示。
图4-1 直接计算
Fig. 4-1 Direct Calculation
图4-2 采用多极展开法计算
Fig. 4-2 Calculation with FMM
在多层的递归算法中，对给定的区域，首先定义包含所有源点的最小立方体(或平面)作为计算区域。先将计算区域按某种方式层层细化为越来越小的
多个子区域。在0层，有一个立方体包含所有的计算主域。第层是把第层的每个立方体分成若干份形成的。一个立方体是否需要再细分，是根据其中包含源点的个数是否少于某一设定值，这个值是根据解题规模的大小而确定。之后再从最后一层开始，将相互作用力的计算分成两个部分，第一部分是与该立方体相邻的立方体，即有公共的边界点，它们之间的作用力需要直接计算。第二部分是与该立方体不相邻的立方体，即没有公共的边界点，它们之间的作用力用FMM计算，将其上的每一单元格中所有粒子的作用归结为某一粒子的作用，之后再进行其上一层的FMM近似计算，如此递归下去直到最上层。其递归计算结构如图4-3所示。
图4-3 多层递归FMM
Fig. 4-3 Multi-level FMM
FMM相关定理
FMM的所有公式，建立在球坐标系上。为适用FMM，定义阶次的球面调和函数：，式中，是连带勒让德函数，可以用罗巨格(Rodrigues)公式定义
式中，是次勒让德多项式。
下面给出的一系列FMM相关定理适于域积分项的计算。其中，多极展开和局部展开定理，描述了电荷集在远处的电场只与电荷集等效的总电荷
(球心处)大小有关，而与其分布形式无关，这与力学的圣维南原理相当。FMM主要依赖多极展开和局部展开的平移。相关定理叙述如下：
(1)多极展开定理
假设有个强度为的电荷分别位于球坐标分别为的