A stable matrix version of the fast multipole method: stabilization strategies and examples
A stable matrix version of the fast multipole method: stabilization strategies and examples
复制标题
DOI：
10.1553/etna_vol54s581
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Difeng Cai;J. Xia
中科院分区：
文献类型：
--
作者：
Difeng Cai;J. Xia
快速多极法是求解离散核函数相关矩阵向量积的一种有效方法。该方法涉及由一系列较小矩阵（为方便起见称为生成器）给出的底层FMM矩阵。虽然在设计和应用FMM技术方面已经做了大量的工作，但对FMM的稳定性和稳定的FMM矩阵分解的研究却很少。在这项工作中，我们提出了导致FMM矩阵稳定操作的技术。一个关键的目标是给出稳定策略，该策略可用于在FMM中提供满足某些稳定性要求的低秩近似和平移关系。fmm中使用的标准泰勒展开产生了易受不稳定性影响的基生成器。在这里，我们引入了一些比例因子来控制发电机的相关规范，并对入口幅度的界限进行了严格的分析。第二个目标是以一维情况为例，提供满足某些稳定性条件的FMM矩阵的直观构造，然后将FMM矩阵转换为允许稳定ulv型分解的层次半可分（HSS）形式。这弥合了FMM和稳定FMM矩阵分解之间的差距。HSS构造是解析完成的，不需要昂贵的代数压缩。给出了相关的稳定性研究，结果表明所得到的矩阵形式适合于稳定运行。注意，基本的稳定思想也适用于更高的维度。大量的数值试验证明了该方法的可靠性和准确性。
The fast multipole method (FMM) is an efficient method for evaluating matrix-vector products related to certain discretized kernel functions. The method involves an underlying FMM matrix given by a sequence of smaller matrices (called generators for convenience). Although there has been extensive work in designing and applying FMM techniques, the stability of the FMM and the stable FMM matrix factorization have rarely been studied. In this work, we propose techniques that lead to stable operations with FMM matrices. One key objective is to give stabilization strategies that can be used to provide low-rank approximations and translation relations in the FMM satisfying some stability requirements. The standard Taylor expansions used in FMMs yield basis generators susceptible to instability. Here, we introduce some scaling factors to control the relevant norms of the generators and give a rigorous analysis of the bounds of the entrywise magnitudes. The second objective is to use the one-dimensional case as an example to provide an intuitive construction of FMM matrices satisfying some stability conditions and then convert an FMM matrix into a hierarchically semiseparable (HSS) form that admits stable ULV-type factorizations. This bridges the gap between the FMM and stable FMM matrix factorizations. The HSS construction is done analytically and does not require expensive algebraic compression. Relevant stability studies are given, which show that the resulting matrix forms are suitable for stable operations. Note that the essential stabilization ideas are also applicable to higher dimensions. Extensive numerical tests are given to illustrate the reliability and accuracy.