Vol. 173

Front:[PDF file] Back:[PDF file]
Latest Volume
All Volumes
All Issues
2022-03-09

Massively Parallel Multilevel Fast Multipole Algorithm for Extremely Large-Scale Electromagnetic Simulations: a Review

By Wei-Jia He, Xiao-Wei Huang, Ming-Lin Yang, and Xin-Qing Sheng
Progress In Electromagnetics Research, Vol. 173, 37-52, 2022
doi:10.2528/PIER22011202

Abstract

Since the first working multilevel fast multipole algorithm (MLFMA) for electromagnetic simulations was proposed by Chew's group in 1995, this algorithm has been recognized as one of the most powerful tools for numerical solutions of extremely large electromagnetic problems with complex geometries. It has been parallelized with different strategies to explore the computing power of supercomputers, increasing the size of solvable problems from millions to tens of billions of unknowns, thereby addressing the crucial demand arising from practical applications in a sense. This paper provides a comprehensive review of state-of-the-art parallel approaches of the MLFMA, especially on a newly proposed ternary parallelization scheme and its acceleration on graphics processing unit (GPU) clusters. We discuss and numerically study the advantages of the ternary parallelization scheme and demonstrate its flexibility and efficiency.

Citation


Wei-Jia He, Xiao-Wei Huang, Ming-Lin Yang, and Xin-Qing Sheng, "Massively Parallel Multilevel Fast Multipole Algorithm for Extremely Large-Scale Electromagnetic Simulations: a Review," Progress In Electromagnetics Research, Vol. 173, 37-52, 2022.
doi:10.2528/PIER22011202
http://www.jpier.org/PIER/pier.php?paper=22011202

References


    1. Mautz, J. R. and R. F. Harrington, "H-field, E-field, and combined field solutions for conducting bodies of revolution," Aeu., Vol. 32, No. 4, 157-164, Apr. 1978.
    doi:

    504 Gateway Time-out


    2. Rao, S. M., D. R. Wilton, and A. W. Glisson, "Electromagnetic scattering by surfaces of arbitrary shape," IEEE Trans. Antennas Propag., Vol. 30, No. 3, 409-418, May 1982.
    doi:The server didn't respond in time.

    3. Sarkar, T., E. Arvas, and S. Rao, "Application of FFT and the conjugate gradient method for the solution of electromagnetic radiation from electrically large and small conducting bodies," IEEE Trans. Antennas Propag., Vol. 34, No. 5, 635-640, May 1986.
    doi:

    4. Coifman, R., V. Rokhlin, and S. Wandzura, "The fast multipole method for the wave equation: A pedestrian prescription," IEEE Antennas Propag. Mag., Vol. 35, No. 3, 7-12, Jun. 1993.

    5. Song, J. M. and W. C. Chew, "Multilevel fast multipole algorithm for solving combined field integral equations of electromagnetic scattering," Microw. Opt. Tech. Lett., Vol. 10, 14-19, Sep. 1995.

    6. Song, J. M., C. C. Lu, and W. C. Chew, "Multilevel fast multipole algorithm for electromagnetic scattering by large complex objects," IEEE Trans. Antennas Propag., Vol. 45, No. 10, 1488-1493, Oct. 1997.

    7. Wu, F., Y. Zhang, Z. Z. Oo, and E. Li, "Parallel multilevel fast multipole method for solving large-scale problems," IEEE Antennas Propag. Mag., Vol. 47, No. 4, 110-118, Aug. 2005.

    8. Velamparainbil, S. V., J. E. Schutt-Aine, J. G. Nickel, J. M. Song, and W. C. Chew, "Solving large scale electromagnetic problems using a linux cluster and parallel MLFMA," IEEE International Symposium on Antennas and Propagation Digest, Vol. 1, 636-639, Jul. 1999.

    9. Donepudi, K. C., J. M. Jin, S. Velamparambil, J. M. Song, and W. C. Chew, "A higher order parallelized multilevel fast multipole algorithm for 3-D scattering," IEEE Trans. Antennas Propag., Vol. 49, No. 7, 1069-1078, Jul. 2001.

    10. Velamparambil, S., W. C. Chew, and J. M. Song, "10 million unknowns: Is it that big?," IEEE Antennas Propag. Mag., Vol. 45, No. 2, 43-58, Apr. 2003.

    11. Velamparambil, S. and W. C. Chew, "Analysis and performance of a distributed memory multilevel fast multipole algorithm," IEEE Trans. Antennas Propag., Vol. 53, No. 8, 2719-2727, Aug. 2005.

    12. Gurel, L. and O. Ergul, "Fast and accurate solutions of extremely large integral-equation problems discretised with tens of millions of unknowns," Electron. Lett., Vol. 43, No. 9, 499-500, Apr. 2007.

    13. Waltz, C., K. Sertel, M. A. Carr, B. C. Usner, and J. L. Volakis, "Massively parallel fast multipole method solutions of large electromagnetic scattering problems," IEEE Trans. Antennas Propag., Vol. 55, No. 6, 1810-1816, Jun. 2007.

    14. Hu, J., Z. P. Nie, L. Lei, J. Hu, X. D. Gong, and H. P. Zhao, "Fast 3D EM scattering and radiation solvers based on MLFMA," J. Syst. Eng. Electron., Vol. 19, No. 2, 252-258, Apr. 2008.

    15. Pan, X. M. and X. Q. Sheng, "A sophisticated parallel MLFMA for scattering by extremely large targets," IEEE Antennas Propag. Mag., Vol. 50, No. 3, 129-138, Jun. 2008.

    16. Ergul, O. and L. Gurel, "Efficient parallelization of the multilevel fast multipole algorithm for the solution of large-scale scattering problems," IEEE Trans. Antennas Propag., Vol. 56, No. 8, 2335-2345, Aug. 2008.

    17. Fostier, J. and F. Olyslager, "An asynchronous parallel MLFMA for scattering at multiple dielectric objects," IEEE Trans. Antennas Propag., Vol. 56, No. 8, 2346-2355, Aug. 2008.

    18. Pan, X. M., W. C. Pi, M. L. Yang, Z. Peng, and X. Q. Sheng, "Solving problems with over one billion unknowns by the MLFMA," IEEE Trans. Antennas Propag., Vol. 60, No. 5, 2571-2574, May 2012.

    19. Fostier, J. and F. Olyslager, "Provably scalable parallel multilevel fast multipole algorithm," Electron. Lett., Vol. 44, No. 19, 1111-1113, Sep. 2008.

    20. Fostier, J. and F. Olyslager, "Full-wave electromagnetic scattering at extremely large 2-D objects," Electron. Lett., Vol. 45, No. 5, 245-246, Feb. 2009.

    21. Ergul, O. and L. Gurel, "Hierarchical parallelisation strategy for multilevel fast multipole algorithm in computational electromagnetics," Electron. Lett., Vol. 44, No. 6, 3-4, 2008.

    22. Ergul, O. and L. Gurel, "A hierarchical partitioning strategy for an efficient parallelization of the multilevel fast multipole algorithm," IEEE Trans. Antennas Propag., Vol. 57, No. 6, 1740-1750, Jun. 2009.

    23. Ergul, O. and L. Gurel, "Rigorous solutions of electromagnetics problems involving hundreds of millions of unknowns," IEEE Antennas Propag. Mag., Vol. 53, No. 1, 18-27, Feb. 2011.

    24. Ergul, O. and L. Gurel, "Hierarchical parallelization of the multilevel fast multipole algorithm (MLFMA)," Proc. IEEE, Vol. 101, No. 2, 332-341, 2013.

    25. Michiels, B., J. Fostier, I. Bogaert, and D. D. Zutter, "Weak scalability analysis of the distributed-memory parallel MLFMA," IEEE Trans. Antennas Propag., Vol. 61, No. 11, 5567-5574, Nov. 2013.

    26. Michiels, B., I. Bogaert, J. Fostier, and D. De Zutter, "A well-scaling parallel algorithm for the computation of the translation operator in the MLFMA," IEEE Trans. Antennas Propag., Vol. 62, No. 5, 2679-2687, 2014.

    27. Michiels, B., J. Fostier, I. Bogaert, and D. D. Zutter, "Full-wave simulations of electromagnetic scattering problems with billions of unknowns," IEEE Trans. Antennas Propag., Vol. 57, No. 6, 796-798, Feb. 2015.

    28. Melapudi, V., B. Shanker, S. Seal, and S. Aluru, "A scalable parallel wideband MLFMA for efficient electromagnetic simulations on large scale clusters," IEEE Trans. Antennas Propag., Vol. 59, No. 7, 2565-2577, 2011.

    29. Hughey, S., H. M. Aktulga, M. Vikram, M. Lu, B. Shanker, and E. Michielssen, "Parallel wideband MLFMA for analysis of electrically large, non-uniform, multiscale structures," IEEE Trans. Antennas Propag., Vol. 67, No. 2, 1094-1107, 2018.

    30. Yang, M. L., B. Y. Wu, H. W. Gao, and X. Q. Sheng, "A ternary parallelization approach of MLFMA for solving electromagnetic scattering problems with over 10 billion unknowns," IEEE Trans. Antennas Propag., Vol. 67, No. 11, 6965-6978, 2019.

    31. Liu, R. Q., X. W. Huang, Y. L. Du, M. L. Yang, and X. Q. Sheng, "Massively parallel discontinuous galerkin surface integral equation method for solving large-scale electromagnetic scattering problems," IEEE Trans. Antennas Propag., Vol. 69, No. 9, 6122-6127, 2021.

    32. Huang, X. W., M. L. Yang, and X. Q. Sheng, "A simplified discontinuous Galerkin self-dual integral equation formulation for electromagnetic scattering from extremely large IBC objects," IEEE Trans. Antennas Propag., 2021, doi: 10.1109/TAP.2021.3137485.

    33. Taboada, J. M., L. Landesa, F. Obelleiro, J. L. Rodriguez, J. M. Bertolo, M. G. Araujo, J. C. Mouriño, and A. Gomez, "High scalability FMM-FFT electromagnetic solver for supercomputer systems," IEEE Antennas Propag. Mag., Vol. 51, No. 6, 20-28, Dec. 2009.

    34. Araújo, M. G., J. Taboada, F. Obelleiro, J. M. Bértolo, L. Landesa, J. Rivero, and J. L. Rodríguez, "Supercomputer aware approach for the solution of challenging electromagnetic problems," Progress In Electromagnetics Research, Vol. 101, 241-256, 2010.

    35. Taboada, J., M. G. Araújo, J. M. Bértolo, L. Landesa, F. Obelleiro, and J. L. Rodríguez, "MLFMA-FFT parallel algorithm for the solution of large-scale problems in electromagnetic (Invited Paper)," Progress In Electromagnetics Research, Vol. 105, 15-30, 2010.

    36. Taboada, J. M., M. G. Araújo, F. Obelleiro, J. L. Rodríguez, and L. Landesa, "MLFMA-FFT parallel algorithm for the solution of extremely large problems in electromagnetics," Proc. IEEE, Vol. 101, No. 2, 350-363, Feb. 2013.

    37. Hansen, T. B., "Translation operator based on Gaussian beams for the fast multipole method in three dimensions," Wave Motion, Vol. 50, No. 5, 940-954, Jul. 2013.

    38. Hansen, T. B. and O. Borries, "Gaussian translation operator in a multilevel scheme," Radio Sci., Vol. 50, No. 8, 754-763, Aug. 2015.

    39. Eibert, T. F. and T. B. Hansen, "Propagating plane-wave fast multipole translation operators revisited - Standard, windowed, Gaussian beam," IEEE Trans. Antennas Propag., Vol. 69, No. 9, Sep. 2021.

    40. Cwikla, M., J. Aronsson, and V. Okhmatovski, "Low-frequency MLFMA on graphics processors," IEEE Antennas Wireless Propag. Lett., Vol. 9, 8-11, 2010.

    41. Guan, J., Y. Su, and J. M. Jin, "An openMP-CUDA implementation of multilevel fast multipole algorithm for electromagnetic simulation on multi-GPU computing systems," IEEE Trans. Antennas Propag., Vol. 61, No. 7, 3607-3616, 2013.

    42. Tran, N. and O. Kilic, "Parallel implementations of multilevel fast multipole algorithm on graphical processing unit cluster for large-scale electromagnetics objects," Appl. Comput. Electromag. Soc. J., Vol. 1, No. 4, 145-148, 2016.

    43. Phan, T., N. Tran, and O. Kilic, "Multi-level fast multipole algorithm for 3-D homogeneous dielectric objects using MPI-CUDA on GPU cluster," Appl. Comput. Electromag. Soc. J., Vol. 33, No. 3, 335-338, 2018.

    44. Hesford, A. J. and W. C. Chew, "Fast inverse scattering solutions using the distorted Born iterative method and the multilevel fast multipole algorithm," Journal of the Acoustical Society of America, Vol. 128, No. 2, 679-690, 2010.

    45. Roohani Ghehsareh, H., S. Kamal Etesami, and M. Hajisadeghi Esfahani, "Numerical investigation of electromagnetic scattering problems based on the compactly supported radial basis functions," Zeitschrift für Naturforschung A, Vol. 71, No. 8, 677-690, 2016.