A fast polynomial representation for the translation operators of an MLFMA

Diagonal translation operators form the core of the dynamic multilevel fast multipole algorithm (MLFMA). An application of the MLFMA requires knowledg e of these operators over a large number of samples. In fact, the cost of a naive evaluation is O(N-3/2), where N is the number of unknowns. More impo rtantly, 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 poly nomial representations of the diagonal operators which require O(rootN) sto rage, and which can be computed in O(N log(l/epsilon)) time, where epsilon is the desired precision. We report some numerical results demonstrating th e performance of the new representations. (C) 2001 John Wiley & Sons, Inc.