volume | PIER Journals

Abstract

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

6. Sylvand, G., "Performance of a parallel implementation of the FMM for electromagnetics applications," Int. J. Numer. Meth. Fluids, Vol. 43, 865-879, 2003. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

Miss Marta Gomez Araujo

Dr. Jose Taboada

Professor Fernando Obelleiro

Dr. Jose Manuel Bertolo

Prof. Luis Landesa

Dr. Javier Rivero

Prof. Jose Luis Rodriguez