On the parallelization of electrodynamic multilevel fast multipole method on distributed memory computers

In recent years, the Multilevel Fast Multipole Method (MLFMA) has been developed into one of the most powerful techniques for accelerating the iterative solution of integral equations of electromagnetics. It has been shown that the MLFMA reduces the computational complexity of a matrix-vector multiply from O(N²) to O(N log N), where N is the number of unknowns. In an attempt to extend the range of problems that can be solved using this technique, we have recently developed an application independent, parallel MLFMA kernel, called ScaleME, for distributed memory computers using MPI. In this paper, we shall discuss the characteristic features which distinguishes it from its static counterpart, such as work required for each level, the size of multipole expansions and interpolation/filtering operations, and their influence in the parallel algorithm design. We shall follow it with a discussion of major issues in the parallelization which are unique to the dynamic MLFMA, such as reducing the memory requirements for translation operators and the reduction of replicated geometric data structures. We shall also briefly discuss the load balancing strategies. Finally, we shall present some representative numerical results from some ScaleME accelerated electromagnetic scattering codes, including a simulation involving 4 million unknowns and that of the radar cross-section computation of a full scale aircraft on a Beowulf class cluster