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 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 57 Issue: 6
  • Publication Date: 2009
  • Doi Number: 10.1109/tap.2009.2019913
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.1740-1750
  • Keywords: Large-scale problems, multilevel fast multipole algorithm, parallelization, scattering problems, surface integral equations, FIELD INTEGRAL-EQUATION, ELECTROMAGNETIC SCATTERING, TRIANGLE, PERFORMANCE, UNKNOWNS, SURFACES, OBJECTS, SHAPE
  • Middle East Technical University Affiliated: No


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.