ITR/SF&IT: Fast Multipole Translation Algorithms for Solution of the 3D Helmholtz Equation

这项建议涉及新的改进，有可能实现显着的速度加快的快速多极方法（FMM）用于解决亥姆霍兹和其他问题，用于模拟电磁学，声学，生物学等遇到的现象，解决更大的问题有希望更好的设计，一方面，和阐明新的物理/生物学的另一方面。由这些方程产生的偏微分方程的离散化产生了大型的方程组，对于这些方程组，直接和迭代求解技术都是昂贵的。由Rokhlin Greengard引入的FMM在科学计算界产生了巨大的兴趣，因为它展示了一种在不依赖离散化的情况下生成结构并实现方程快速求解的方法。尽管它的承诺，该算法还没有实现广泛的实施，许多实际上重要的问题，可以使用承诺的加速。一些研究人员报告说，近似积分都使实施困难，并在实践中，他们已被证明引入稳定性问题。最近，我们推导出的亥姆霍兹方程的多极解的平移和旋转的精确表达式，使快速计算，通过简单的递归。此外，我们已经获得了非常有希望的结果，使创建非常紧密的误差界的平移算子的属性。我们的翻译有相同的渐近复杂性的标准积分表达式，但更小的系数。我们还发现，平移算子可以分解为稀疏递归矩阵的乘积，这可以是我们提出的T（p2）算法的基础。基于这些表达式，我们将开发软件来解决不同的问题，使用FMM。为了推动信息技术革命，我们的软件将在可访问的同行评审论坛上进行详细记录和发布。这种可用性将有助于提高大量从业人员的采用率。

This proposal concerns new improvements that have the potential to achieve significant speed-up for the fast multipole method (FMM) for use in solving the Helmholtz and other problems used to model phenomena encountered in electromagnetics, acoustics, biology etc. Solving larger problems holds promise for better design on the one hand, and elucidation of new physics/biology on the other. Discretizations of the partial differential equations arising from these equations yield large systems of equations for which both direct and iterative solution techniques are expensive.The introduction by Rokhlin & Greengard of the FMM generated tremendous interest in the scientific computing community, as it demonstrated a way to generate structure and achieve fast solution of equations without relying on the discretization. Despite its promise, the algorithm has not achieved widespread implementation for many practically important problems that could use the promised speedups. Some researchers have reported that the approximate integrals both make implementation difficult, and in practice they have been shown to introduce stability problems. We have recently derived exact expressions for the translation and rotation of multipole solutions of the Helmholtz equation, which enable fast computation via simple recursions. Further we have obtained very promising results on the properties of the translation operators that enable creation of very tight error bounds. Our translations have the same asymptotic complexity as the standard integral expressions, but with much smaller coefficients. We have also found that the translation operator can be decomposed into the product of sparse recurrence matrices and this can be the basis for a T(p2) algorithm, which we propose to pursue. Based on these expressions, we will develop software for solution of different problems using the FMM. To be useful in pushing ahead the information technology revolution our software will be well documented and published in accessible peer reviewed forums. Such availability will act to improve adoption by large numbers of practitioners.