Fast polynomial representation for the translation operators of an MLFMA

Abstract

Diagonal translation operators form the core of the dynamic multilevel fast multipole algorithm (MLFMA). An application of the MLFMA requires knowledge of these operators over a large number of samples. In fact, the cost of a naive evaluation is O(N3/2), where N is the number of unknowns. More importantly, in a distributed memory computer, if the operators are precomputed and replicated in every processor, the memory requirements scale as O(Np), where p is the number of processors. In this paper, we construct fast polynomial representations of the diagonal operators which require O(√N) storage, and which can be computed in O(N log (1/q)) time, where q is the desired precision. We report some numerical results demonstrating the performance of the new representations.