×

An efficient blocking M2L translation for low-frequency fast multipole method in three dimensions. (English) Zbl 1348.78026

Summary: We propose an efficient scheme to perform the multipole-to-local (M2L) translation in the three-dimensional low-frequency fast multipole method (LFFMM). Our strategy is to combine a group of matrix-vector products associated with M2L translation into a matrix-matrix product in order to diminish the memory traffic. For this purpose, we first developed a grouping method (termed as internal blocking) based on the congruent transformations (rotational and reflectional symmetries) of M2L-translators for each target box in the FMM hierarchy (adaptive octree). Next, we considered another method of grouping (termed as external blocking) that was able to handle M2L translations for multiple target boxes collectively by using the translational invariance of the M2L translation. By combining these internal and external blockings, the M2L translation can be performed efficiently whilst preservingthe numerical accuracy exactly. We assessed the proposed blocking scheme numerically and applied it to the boundary integral equation method to solve electromagnetic scattering problems for perfectly electrical conductor. From the numerical results, it was found that the proposed M2L scheme achieved a few times speedup compared to the non-blocking scheme.

MSC:

78M16 Multipole methods applied to problems in optics and electromagnetic theory
78M15 Boundary element methods applied to problems in optics and electromagnetic theory
78A45 Diffraction, scattering

Software:

ScalFMM; MKL; BLAS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Rokhlin, V., J. Comput. Phys., 60, 2, 187-207 (1985)
[2] Greengard, L.; Rokhlin, V., J. Comput. Phys., 73, 2, 325-348 (1987)
[3] Demmel, J. W., Applied Numerical Linear Algebra (1997), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 0879.65017
[5] Coulaud, O.; Fortin, P.; Roman, J., J. Comput. Phys., 227, 3, 1836-1862 (2008), http://dx.doi.org/10.1016/j.jcp.2007.09.027, URL http://www.sciencedirect.com/science/article/pii/S0021999107004354
[6] Takahashi, T.; Cecka, C.; Fong, W.; Darve, E., Internat. J. Numer. Methods Engrg., 89, 1, 105-133 (2012)
[7] Darve, E.; Cecka, C.; Takahashi, T., C. R. Mécanique, 339, 2-3, 185-193 (2011), URL http://linkinghub.elsevier.com/retrieve/pii/S1631072110002159
[8] Fong, W.; Darve, E., J. Comput. Phys., 228, 8712-8725 (2009)
[9] Takahashi, T.; Cecka, C.; Darve, E., (Extended Abstracts for Symposium of the International Association for Boundary Element Methods, IABEM 2011 (2011)), 303-308
[11] Agullo, E.; Bramas, B.; Coulaud, O.; Darve, E.; Messner, M.; Takahashi, T., SIAM J. Sci. Comput., 36, 1, C66-C93 (2014)
[12] Yoshida, Ken-ichi, Applications of fast multipole method to boundary integral equation method (2001), Kyoto University, March · Zbl 1014.74078
[13] Epton, M. A.; Dembart, B., SIAM J. Sci. Comput., 16, 4, 865-897 (1995)
[14] (Abramowitz, M.; Stegun, I., Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables, eighth Dover printing (1972), Dover: Dover New York) · Zbl 0543.33001
[15] Messiah, A., Quantum Mechanics: Two Volumes Bound as One (1999), Dover: Dover Mineola, New York, URL http://books.google.co.jp/books?id=4dlWNQEACAAJ
[16] Coifman, R.; Rokhlin, V.; Wandzura, S., IEEE Antennas Propag. Mag., 35, 3, 7-12 (1993)
[17] Song, J.; Lu, C.-C.; Chew, W. C., IEEE Trans. Antennas and Propagation, 45, 10, 1488-1493 (1997)
[22] Henry, G., Optimize for Intel AVX Using Intel Math Kernel Library’s Basic Linear Algebra Subprograms (BLAS) with DGEMM Routine (2012), Aug
[24] Gepner, P.; Gamayunov, V.; Fraser, D. L., Procedia Comput. Sci., 9, 0, 126-135 (2012), Proceedings of the International Conference on Computational Science, ICCS 2012. http://dx.doi.org/10.1016/j.procs.2012.04.014, URL http://www.sciencedirect.com/science/article/pii/S1877050912001354
[25] Rao, S.; Wilton, D.; Glisson, A., IEEE Trans. Antennas and Propagation, 30, 3, 409-418 (1982)
[26] Darve, E., J. Comput. Phys., 160, 1, 195-240 (2000), http://dx.doi.org/10.1006/jcph.2000.6451, URL http://www.sciencedirect.com/science/article/pii/S0021999100964519
[27] Bowman, J. J.; Senior, T. B.A.; Uslenghi, P. L.E., Electromagnetic and Acoustic Scattering by Simple Shapes, Revised ed. (1987), Hemisphere Publishing Corp.: Hemisphere Publishing Corp. New York
[28] Saad, Y.; Schultz, M. H., SIAM J. Sci. Stat. Comput., 7, 856-869 (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.