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

ITR/SF

• 批准号: 0219681
• 负责人: Nail Gumerov
• 金额: $ 45万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-10-01 至 2006-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0219681&HistoricalAwards=false
• 关键词: ITR; SF& Fast; Multipole; Translation

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.

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