The fast multipole method for the wave equation: a pedestrian prescription

Abstract

A practical and complete, but not rigorous, exposition of the fact multiple method (FMM) is provided. The FMM provides an efficient mechanism for the numerical convolution of the Green's 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 O(N/sup 2/) to O(N/sup 3/2/), where N is the dimensionality of the problem's discretization.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>