Revisiting the Fast Multipole Algorithm Error Bounds
William D. Elliott
Abstract
The error bound typically reported for the potential computed in
the Greengard-Rokhlin Fast Multipole Algorithm (FMA) omits
the effects of some of the computations that increase
the error of the overall algorithm. This paper addresses the
error bounds of the overall FMA to include the effects of
computations which contribute to error.
Examining the worst case FMA error by finding the worst case configuration
of charged particle and evaluation point, the paper proves that the series
expansion of the configuration reduces to a simplified multipole
expansion which includes exactly the effects of all FMA
computations. With this result,
this paper argues that the worst case relative error
bound for potential computed in the original FMA is
(1/sqrt(3))^p rather than (1/2)^p
as is typically reported. The variable p is the number of terms
carried in the series expansions. Also, this paper derives the worst case
relative error bound for the force computation, which is
(1/sqrt(3))^p ( p(sqrt(3) + 1) - 1 )
Back to the Scientific Computions Group Home Page