A Hierarchical Partitioning Strategy for an Efficient Parallelization of the Multilevel Fast Multipole Algorithm


Creative Commons License

Erguel O. , Guerel L.

IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION, vol.57, no.6, pp.1740-1750, 2009 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 57 Issue: 6
  • Publication Date: 2009
  • Doi Number: 10.1109/tap.2009.2019913
  • Title of Journal : IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION
  • Page Numbers: pp.1740-1750

Abstract

We present a novel hierarchical partitioning strategy for the efficient parallelization of the multilevel fast multipole algorithm (MLFMA) on distributed-memory architectures to solve large-scale problems in electromagnetics. Unlike previous parallelization techniques, the tree structure of MLFMA is distributed among processors by partitioning both clusters and samples of fields at each level. Due to the improved load-balancing, the hierarchical strategy offers a higher parallelization efficiency than previous approaches, especially when the number of processors is large. We demonstrate the improved efficiency on scattering problems discretized with millions of unknowns. In addition, we present the effectiveness of our algorithm by solving very large scattering problems involving a conducting sphere of radius 210 wavelengths and a complicated real-life target with a maximum dimension of 880 wavelengths. Both of the objects are discretized with more than 200 million unknowns.