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

University Of Maryland, College Park, College Park MD

Investigators

Abstract

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.