The Fast Multipole Method I: Error Analysis and Asymptotic Complexity

This paper is concerned with the application of the fast multipole method (FMM) to the Maxwell equations. This application differs in many aspects from other applications such as the N-body problem, Laplace equation, and quantum chemistry, etc. The FMM leads to a significant speed-up in CPU time with a major reduction in the amount of computer memory needed when performing matrix-vector products. This leads to faster resolution of scattering of harmonic plane waves from perfectly conducting obstacles. Emphasis here is on a rigorous mathematical approach to the problem. We focus on the estimation of the error introduced by the FMM and a rigorous analysis of the complexity (O(n log n)) of the algorithm. We show that error estimates reported previously are not entirely satisfactory and provide sharper and more precise estimates.