Efficient fast multipole method for low-frequency scattering.

*(English)*Zbl 1073.65133The solution of the Helmholtz and Maxwell equations using integral formulations requires to solve large complex linear systems. A direct solution of those problems using a Gauss elimination is practical only for very small systems with few unknowns. The use of an iterative method such as GMRES can reduce the computational expense. Most of the expense is then computing large complex matrix vector products. The cost can be further reduced by using the fast multipole method which accelerates the matrix vector product. For a linear system of size \(N\), the use of an iterative method combined with the fast multipole method reduces the total expense of the computation to \(N\log N\). There exist two versions of the fast multipole method: one which is based on a multipole expansion of the interaction kernel \(\exp\iota kr/r\) and which was first proposed by V. Rokhlin [ibid. 60, 187–207 (1985; Zbl 0629.65122)] and another based on a plane wave expansion of the kernel, first proposed by W. C. Chew, J. M. Jin, C. C. Lu, E. Michielssen and J. M. M. Song [Fast solution emthods in electromagnetics, IEEE Trans. Antenn. Progag. 45, No. 3, 533–543 (1997)]. In this paper, the authors propose a third approach, the stable plane wave expansion, which has a lower computational expense than the multipole expansion and does not have the accuracy and stability problems of the plane wave expansion. The computational complexity is \(N\log N\) as with the other methods.

Reviewer: Xavier Antoine (Vandœuvre-lès-Nancy)

##### MSC:

65N38 | Boundary element methods for boundary value problems involving PDEs |

78A45 | Diffraction, scattering |

35J05 | Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation |

35Q60 | PDEs in connection with optics and electromagnetic theory |

65N12 | Stability and convergence of numerical methods for boundary value problems involving PDEs |

65F10 | Iterative numerical methods for linear systems |

##### Keywords:

fast multipole method; Laplace equation; Maxwell equation; Helmholtz equation; electromagnetic scattering; low-frequency scattering; plane wave; evanescent wave; numerical examples; iterative method; matrix vector product; stability; computational complexity
PDF
BibTeX
XML
Cite

\textit{E. Darve} and \textit{P. Havé}, J. Comput. Phys. 197, No. 1, 341--363 (2004; Zbl 1073.65133)

Full Text:
DOI

##### References:

[1] | Chew, W.C.; Jin, J.M.; Lu, C.C.; Michielssen, E.; Song, J.M.M., Fast solution methods in electromagnetics, IEEE trans. antenn. propag., 45, 3, 533-543, (1997) |

[2] | Rokhlin, V., Rapid solution of integral equations of classical potential theory, J. comput. phys., 60, 2, 187, (1985) · Zbl 0629.65122 |

[3] | Engheta, N.; Murphy, W.; Rokhlin, V.; Vassiliou, M.S., The fast multipole method for (FMM) electromagnetic scattering problems, IEEE trans. antenn. propag., 40, 6, 634-641, (1992) · Zbl 0947.78614 |

[4] | Epton, M.A.; Dembart, B., Multipole translation theory for three-dimensional Laplace and Helmholtz equations, SIAM J. sci. comput., 16, 4, 865-897, (1995) · Zbl 0852.31006 |

[5] | B. Dembart, E. Yip, A 3D fast multipole method for electromagnetics with multiple levels, in: Proceedings of the 11th Annual Review of Progress in Applied Computational Electromagnetics, vol. 1, Monterey, CA, 1995, pp. 621-628 |

[6] | B. Dembart, G. Shubin, A 3D fast multipole method for electromagnetics with multiple levels, Technical document ISSTECH-97-004, Boeing, December 1994 |

[7] | B. Dembart, E. Yip, A 3-D moment method code based on fast multipole, in: URSI Radio Science Meeting Dig., Seattle, WA, 1994, p. 23 |

[8] | Elliott, W.; Board, J., Fast Fourier-transform accelerated fast multipole algorithm, SIAM J. sci. comput., 17, 2, 398-415, (1996) · Zbl 0855.70001 |

[9] | L. Greengard, V. Rokhlin, A new version of the fast multipole method for the Laplace equation in three dimensions, Acta Numer. 229 · Zbl 0889.65115 |

[10] | White, C.; Headgordon, M., Rotating around the quartic angular-momentum barrier in fast multipole method calculations, J. chem. phys., 105, 12, 5061-5067, (1996) |

[11] | Zhao, J.-S.; Chew, W.C., Applying matrix rotation to the three-dimensional low-frequency multilevel fast multipole algorithm, Microw. opt. technol. lett., 26, 2, 105-110, (2000) |

[12] | L. Greengard, J. Huang, V. Rokhlin, S. Wandzura, Accelerating fast multipole methods for low frequency scattering, IEEE Comput. Sci. Engrg. Mag. |

[13] | Zhao, J.-S.; Chew, W.C., Three-dimensional multilevel fast multipole algorithm from static to electrodynamic, Microw. opt. technol. lett., 26, 1, 43-48, (2000) |

[14] | Zhao, J.-S.; Chew, W.C., MLFMA for solving integral equations of 2-D electromagnetic problems from static to electrodynamic, Microw. opt. technol. lett., 20, 5, 306-311, (1999) |

[15] | Zhao, J.-S.; Chew, W.C., Applying LF-MLFMA to solve complex PEC structures, Microw. opt. technol. lett., 28, 3, 155-160, (2001) |

[16] | Rokhlin, V., Rapid solution of integral equations of scattering theory in two dimensions, J. comput. phys., 86, 2, 414-439, (1990) · Zbl 0686.65079 |

[17] | V. Rokhlin, Diagonal forms of translation operators for the Helmholtz equation in three dimensions, Research Report YALEU/DCS/RR-894, Department of Computer Science, Yale University, March 1992 · Zbl 0795.35021 |

[18] | Lu, C.C.; Chew, W.C., A multilevel algorithm for solving boundary-value scattering, Microw. opt. technol. lett., 7, 10, 466-470, (1994) |

[19] | Song, J.; Lu, C.-C.; Chew, W.C., Multilevel fast multipole algorithm for electromagnetic scattering by large complex objects, IEEE trans. antenn. propag., 45, 10, 1488-1493, (1997) |

[20] | Darve, E., The fast multipole method (i): error analysis and asymptotic complexity, SIAM numer. anal., 38, 1, 98-128, (2000) · Zbl 0974.65033 |

[21] | Darve, E., The fast multipole method: numerical implementation, J. comput. phys., 160, 1, 195-240, (2000) · Zbl 0974.78012 |

[22] | Chew, W.C., Fast algorithms for wave scattering developed at the university of illinois’s electromagnetics laboratory, IEEE antenn. propag. mag., 35, 4, 22-32, (1993) |

[23] | Chew, W.C.; Jin, J.; Lu, C.-C.; Michielssen, E.; Song, J., Fast solution methods in electromagnetics, IEEE trans. antenn. propag., 45, 3, 533-543, (1997) |

[24] | Song, J.; Chew, W.C., Multilevel fast-multipole algorithm for solving combined field integral equations of electromagnetic scattering, Microw. opt. technol. lett., 10, 1, 14-19, (1995) |

[25] | Chew, W.C.; Lu, C.-C.; Wang, Y.M., Review of efficient computation of three-dimensional scattering of vector electromagnetic waves, J. opt. soc. am. A, 11, 1528-1537, (1994) |

[26] | C.C. Lu, W.C. Chew, Fast far-field approximation for calculating the RCS of large objects, Microw. Opt. Technol. Lett. 8 (5) |

[27] | J. Song, C.-C. Lu, W.C. Chew, S. Lee, Fast Illinois solver code (FISC) solves problems of unprecedented size at the center for computational electromagnetics, University of Illinois Technical Report CCEM-23-97, University of Illinois, Urbana Champaign, IL, 1997 |

[28] | Song, J.; Lu, C.; Chew, W.C.; Lee, S., Fast illinois solver code (FISC), IEEE antenn. propag. mag., 40, 3, 27-33, (1998) |

[29] | Lu, C.; Chew, W.C., A multilevel algorithm for solving a boundary integral equation of wave scattering, Microw. opt. technol. lett., 7, 10, 466-470, (1994) |

[30] | Wagner, R.L.; Chew, W.C., A ray-propagation fast multipole algorithm, Microw. opt. technol. lett., 7, 10, 435-438, (1994) |

[31] | Song, J.; Chew, W.C., Error analysis for the truncation of multipole expansion of vector green’s functions, IEEE microw. wireless comp. lett., 11, 7, 311-313, (2001) |

[32] | Koc, S.; Song, J.; Chew, W.C., Error analysis for the numerical evaluation of the diagonal forms of the scalar spherical addition theorem, SIAM J. numer. anal., 36, 3, 906-921, (1999) · Zbl 0924.65116 |

[33] | Solvason, D.; Petersen, H., Error estimates for the fast multipole method, J. statist. phys., 86, 1-2, 391-420, (1997) · Zbl 0952.82509 |

[34] | Amini, S.; Profit, A., Analysis of the truncation errors in the fast multipole method for scattering problems, J. comput. appl. math., 115, 1-2, 23-33, (2000) · Zbl 0973.65092 |

[35] | Dembart, B.; Yip, E., The accuracy of fast multipole methods for maxwell’s equations, IEEE comput. sci. engrg., 5, 3, 48-56, (1998) |

[36] | Bindiganavale, S.; Volakis, J., Guidelines for using the fast multipole method to calculate the RCS of large objects, Microw. opt. technol. lett., 11, 4, 190-194, (1996) |

[37] | Ohnuki, S.; Chew, W.C., A study of the error controllability of MLFMA, antennas and propagation society, IEEE. int. symp., 3, 774-777, (2001) |

[38] | B. Hu, W.C. Chew, Fast inhomogeneous plane wave algorithm for multi-layered medium problems, in: IEEE Antennas and Propagation Society International Symposium, Transmitting Waves of Progress to the Next Millennium, Salt Lake City, UT, 2000, pp. 606-609 |

[39] | B. Hu, W.C. Chew, E. Michielssen, J. Zhao, Fast inhomogeneous plane wave algorithm (FIPWA) for the fast analysis of two-dimensional scattering problems, University of Illinois, Urbana |

[40] | Hu, B.; Chew, C.; Michielssen, W.E.; Zhao, J., Fast inhomogeneous plane wave algorithm for the fast analysis of two-dimensional scattering problems, Radio sci., 34, 4, 759-772, (1999) |

[41] | Hu, B.; Chew, W.C., Fast inhomogeneous plane wave algorithm for electromagnetic solutions in layered medium structures: two-dimensional case, Radio sci., 35, 1, 31-43, (2000) |

[42] | Hu, B.; Chew, C.; Velamparambil, W.S., Fast inhomogeneous plane analysis of electromagnetic wave algorithm for the scattering, Radio sci., 36, 6, 1327-1340, (2001) |

[43] | Hu, B.; Chew, W.C., Fast inhomogeneous plane wave algorithm for scattering from objects above the multilayered medium, IEEE trans. geosci. remote sensing, 39, 5, 1028-1038, (2001) |

[44] | N. Yarvin, V. Rokhlin, Generalized Gaussian quadratures and singular value decompositions of integral operators, Technical Report 1109, Department of Computer Science Research Report, Yale University, 1996 · Zbl 0932.65020 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.