zbMATH — the first resource for mathematics

Analysis-based fast numerical algorithms of applied mathematics. (English) Zbl 0839.65127
Chatterji, S. D. (ed.), Proceedings of the international congress of mathematicians, ICM ’94, August 3-11, 1994, Zürich, Switzerland. Vol. II. Basel: Birkhäuser. 1460-1467 (1995).
The purpose of this article is to give a brief and complete, but not rigorous, exposition of the fast multipole method (FMM) for the Helmholtz equation. For purposes of demonstration, we consider the scalar wave equation with Dirichlet boundary conditions on the surface of a scatterer. The FMM provides an efficient mechanism for the numerical convolution of the Green function for the Helmholtz equation with a source distribution and can be used to radically accelerate the iterative solution of boundary integral equations. In the simple single-stage form presented here, it reduces the computational complexity of the convolution from order \(N^2\) to order \(N^{3/2}\), where \(N\) is the number of nodes in the discretization of the problem. By implementing a multistage FMM, the complexity can be further reduced to order \(N\log N\). However, even for problems that have an order of magnitude more variables than those currently tractable using dense matrix techniques \((N\approx 10^5)\), we estimate that the performance of a carefully implemented single-stage algorithm should be near optimal.
For the entire collection see [Zbl 0829.00015].

65N38 Boundary element methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65Y20 Complexity and performance of numerical algorithms