It is a proven fact that The Fast Fourier Transform (FFT) extension of the conventional Fast Multipole Method (FMM) reduces the matrix vector product (MVP) complexity and preserves the propensity for parallel scaling of the single level FMM. In this paper, an efficient parallel strategy of a nested variation of the FMMFFT algorithm that reduces the memory requirements is presented. The solution provided by this parallel implementation for a challenging problem with more than 0.5 billion unknowns has constituted the world record in computational electromagnetics (CEM) at the beginning of 2009.
1. Coifman, R., V. Rokhlin, and S. Wanzura, "The fast multipole method for the wave equation: A pedestrian prescription," IEEE Antennas Propagat. Mag., Vol. 35, No. 3, 7-12, Jun. 1993. doi:10.1109/74.250128
2. Song, J. M. and W. C. Chew, "Multilevel fast multipole algorithm for solving combined eld integral equations of electromagnetic scattering," Microw. Opt. Tech. Lett., Vol. 10, 14-19, Sep. 1995. doi:10.1002/mop.4650100107
3. Song, J. M., C. C. Lu, W. C. Chew, and S. Lee, "Fast Illinois solver code (FISC)," IEEE Antennas Propag. Mag., Vol. 40, No. 3, 27-34, Jun. 1998. doi:10.1109/74.706067
4. Velamparambil, S., 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 Antennas Propag. Soc. Int. Symp., Vol. 1, 636-639, 1999.
5. Velamparambil, S., W. C. Chew, and J. M. Song, "10 million unknowns: Is it that big?," IEEE Antennas Propagat. Mag., Vol. 45, No. 3, 43-58, Apr. 2003. doi:10.1109/MAP.2003.1203119
6. Sylvand, G., "Performance of a parallel implementation of the FMM for electromagnetics applications," Int. J. Numer. Meth. Fluids, Vol. 43, 865-879, 2003.
7. Velamparambil, S. and W. C. Chew, "Analysis and performance of a distributed memory multilevel fast multipole algorithm," IEEE Trans. Antennas Propagt., Vol. 53, No. 8, 2719-2727, 2005. doi:10.1109/TAP.2005.851859
8. Pan, X. M. and X. Q. Sheng, "A highly effcient parallel approach of multi-level fast multipole algorithm," Journal of Electromagnetic Waves and Applications, Vol. 20, No. 8, 1081-1092, 2006. doi:10.1163/156939306776930321
9. Wang, P. and Y. J. Xie, "Scattering and radiation problem of surface/surface junction structure with multilevel fast multipole algorithm," Journal of Electromagnetic Waves and Applications, Vol. 20, No. 15, 2189-2200, 2006. doi:10.1163/156939306779322567
10. Gurel, L. and O. Ergul, "Fast and accurate solutions of extremely large integral-equation problems discretised with tens of millions of unknowns," Electronics Letters, Vol. 43, No. 9, 499-500, Apr. 2007. doi:10.1049/el:20070639
11. Pan, X.-M. and X. X.-Q. Sheng, "A sophisticated parallel MLFMA for scattering by extremely large targets," IEEE Antennas Propagat. Mag., Vol. 50, 129-138, Jun. 2008. doi:10.1109/MAP.2008.4563583
12. Ergul, O. and L. Gurel, "Efficient parallelization of the multilevel fast multipole algorithm for the solution of large-scale scattering problems," IEEE Trans. Antennas Propagt., Vol. 56, 2335-2345, Aug. 2008. doi:10.1109/TAP.2008.926757
13. Gurel, L., O. Ergul, A. Unal, and T. Malas, "Fast and accurate analysis of large metamaterial structures using the multilevel fast multipole algorithm," Progress In Electromagnetics Research, Vol. 95, 179-198, 2009. doi:10.2528/PIER09060106
14. Wagner, R., J. M. Song, and W. C. Chew, "Montecarlo simulation of electromagnetic scattering from two-dimensional random rough surfaces," IEEE Trans. Antennas Propagt., Vol. 45, No. 2, 235-245, Feb. 1997. doi:10.1109/8.560342
15. 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 Propagt., Vol. 55, No. 6, 1810-1816, Jun. 2007. doi:10.1109/TAP.2007.898511
16. Taboada, J. M., L. Landesa, F. Obelleiro, J. L. Rodriguez, J. M. Bertolo, M. G. Araujo, J. C. Mourino, and A. Gomez, "High scalability FMM-FFT electromagnetic solver for supercomputer systems," IEEE Antennas Propagat. Mag., Dec. 2009.
17. Saad, Y. and M. Schultz, "GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems," SIAMJ. Sci. Statist. Comput., Vol. 7, 856-869, 1986. doi:10.1137/0907058
18. Rodriguez, J. L., M. G. Araujo, J. M. Taboada, L. Landesa, and F. Obelleiro, "On the use of the singular value decomposition in the fast multipole method," IEEE Trans. Antennas Propagt., Vol. 56, No. 8, 2325-2334, Aug. 2008. doi:10.1109/TAP.2008.926761
19. Rao, S. M., D. R. Wilton, and A. W. Glisson, "Electromagnetic scattering by surfaces of arbitrary shape," IEEE Trans. Antennas Propagat., Vol. 30, 409-418, May 1982. doi:10.1109/TAP.1982.1142818