×

zbMATH — the first resource for mathematics

The fast multipole method: Numerical implementation. (English) Zbl 0974.78012
The paper studies algorithmic problems and computational aspects for solving integral equations for electromagnetic scattering problems with the fast multipole method. The paper analyses several techniques to reduce the complexity constant of the method and provides impressive numerical results.

MSC:
78M25 Numerical methods in optics (MSC2010)
65R10 Numerical methods for integral transforms
78A25 Electromagnetic theory, general
65N38 Boundary element methods for boundary value problems involving PDEs
65Y20 Complexity and performance of numerical algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Grama, A.; Kumar, V.; Sameh, A., Parallel hierarchical solvers and preconditioners for boundary-element methods, SIAM J. sci. comput., 20, 337, (1999) · Zbl 0919.65068
[2] Nakano, A., Parallel multilevel preconditioned conjugate-gradient approach to variable-charge molecular-dynamics, Comput. phys. commun., 104, 59, (1997)
[3] Boschitsch, A.H.; Fenley, M.O.; Olson, W.K., A fast adaptive multipole algorithm for calculating screened Coulomb (Yukawa) interactions, J. comput. phys., 151, 212, (1999) · Zbl 1017.92500
[4] Alléon, G.; Benzi, M.; Giraud, L., Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics, (April 1997)
[5] Alpert, B.; Jakob-Chien, R., A fast spherical filter with uniform resolution, J. comput. phys., 136, 580, (1997) · Zbl 0885.65016
[6] Benzi, M.; Tuma, M., A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. sci. comput., 19, 968, (1998) · Zbl 0930.65027
[7] Johnson, B.G., The continuous fast multipole method: large-scale density-functional calculations on parallel computing platforms, ABS. papers am. chem. soc., 213, 272, (1997)
[8] Johnson, B.G.; Graham, R.L., The parallel continuous fast multipole method, ABS. papers am. chem. soc., 213, 25, (1997)
[9] Bindiganavale, S.S.; Volakis, J.L., Comparison of three fmm techniques for solving hybrid fe-bi systems, IEEE antennas propag. mag., 39, 47, (1997)
[10] Bucci, O.M.; Franceschetti, G., On the degrees of freedom of scattered fields, IEEE trans. antennas propag., 37, 918, (1989) · Zbl 1058.78503
[11] Bucci, O.M.; Gennarelli, C.; Riccio, R.; Savarese, C., Electromagnetic fields interpolation from nonuniform samples over spherical and cylindrical surfaces, IEEE proc. microwave antennas propag., 141, 77, (1994)
[12] Bucci, O.M.; Gennarelli, C.; Savarese, C., Optimal interpolation of radiated fields over a sphere, IEEE trans. antennas propag., AP-39, 1633, (1991)
[13] Ochsenfeld, C.; White, C.A.; Headgordon, M., Linear and sublinear scaling formation of hartree – fock type exchange matrices, J. chem. phys., 109, 1663, (1998)
[14] White, C.A.; Johnson, B.G.; Gill, P.M.W.; Headgordon, M., A generalized fast multipole approach for Hartree-Fock and density-functional computations: comment, Chem. phys. lett., 248, 482, (1996)
[15] White, C.A.; Johnson, B.G.; Gill, P.M.W.; Headgordon, M., Linear scaling density-functional calculations via the continuous fast multipole method, Chem. phys. lett., 253, 268, (1996)
[16] White, C.A.; Headgordon, M., Derivation and efficient implementation of the fast multipole method, J. chem. phys., 101, 6593, (1994)
[17] White, C.A.; Headgordon, M., Fractional tiers in fast multipole method calculations, Chem. phys. lett., 257, 647, (1996)
[18] White, C.A.; Headgordon, M., Rotating around the quartic angular-momentum barrier in fast multipole method calculations, J. chem. phys., 105, 5061, (1996)
[19] Chew, W.C.; Wang, Y.M.; Gürel, L., Recursive algorithm for wave-scattering solutions using windowed addition theorem, J. electromag. waves appl., 6, 1537, (1992)
[20] Chow, E.; Saad, Y., Approximate invese preconditioners via sparse – sparse iterations, SIAM J. sci. comput., 19, 995, (1998) · Zbl 0922.65034
[21] Coifman, R.; Rokhlin, V.; Wandzura, S., The fast multipole method for the wave equation: A Pedestrian prescription, IEEE antennas propag. mag., 35, 7, (1993)
[22] E. Darve, The fast multipole method (i): Error analysis and asymptotic complexity, SIAM Numer. Anal, to appear. · Zbl 0974.65033
[23] Dembart, B.; Shubin, G.R., A 3d fast multipole method for electromagnetics with multiple levels, (December 1994)
[24] B. Dembart, and, 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, Monterey, CA, March 1995, Vol, 1, p, 621.
[25] Dutt, A.; Gu, M.; Rokhlin, V., Fast algorithms for polynomial interpolation, integration and differentiation, SIAM J. numer. anal., 33, (1996) · Zbl 0862.65005
[26] Engheta, N.; Murphy, W.D.; Rokhlin, V.; Vassiliou, M.S., The fast multipole method (fmm) for electromagnetic scattering problems, IEEE trans. antennas propag., 40, 634, (1992) · Zbl 0947.78614
[27] Smith, E.R., Fast moment methods for general potentials in molecular dynamics, Mol. phys., 86, 769, (1995)
[28] Francia, G.T.D., Directivity, super-gain and information, IRE trans. antennas propag., 4, 473, (1956)
[29] Francia, G.T.D., Degrees of freedom of an image, J. opt. soc. am., 59, 779, (1969)
[30] Greengard, L., Fast algorithms for classical physics, Science, 265, 909, (1994) · Zbl 1226.65116
[31] Greengard, L.; Huang, J.; Rokhlin, V.; Wandzura, S., Accelerating fast multipole methods for low frequency scattering, IEEE comput. sci. eng. mag., (July 1998)
[32] Grote, M.J.; Huckle, T., Parallel preconditioning with sparse approximate inverses, SIAM J. sci. comput., 18, 838, (1997) · Zbl 0872.65031
[33] Schwichtenberg, H.; Winter, G.; Wallmeier, H., Acceleration of molecular mechanic simulation by parallelization and fast multipole techniques, Parallel comput., 25, 535, (1999) · Zbl 1047.68641
[34] Petersen, H.G.; Soelvason, D.; Perram, J.W., The very fast multipole method, J. chem. phys., 101, 8870, (1994)
[35] Petersen, H.G.; Soelvason, D.; Perram, J.W.; Smith, E.R., Error-estimates for the fast multipole method. 1. the 2 dimensional case, Proc. roy. soc. London ser. A, 448, 389, (1995) · Zbl 0831.65135
[36] Petersen, H.G.; Smith, E.R.; Soelvason, D., Error-estimates for the fast multipole method. 2. the 3 dimensional case, Proc. roy. soc. London ser. A, 448, 401, (1995) · Zbl 0831.65136
[37] Board, J.A., Introduction to “a fast algorithm for particle simulations”, J. comput. phys., 135, 279, (1997) · Zbl 0925.70013
[38] Lee, J.Y.; Jeong, K., A parallel Poisson solver using the fast multipole method on networks of workstations, Comput. math. appl., 36, 47, (1998) · Zbl 0932.65119
[39] Knab, J.J., Interpolation of band-limited functions using the approximate prolate series, IEEE trans. inform. theory, 717, (1979) · Zbl 0422.94009
[40] Knab, J.J., The sampling window, IEEE trans. inform. theory, 157, (1983) · Zbl 0499.94006
[41] Koc, S.; Song, J.M.; Chew, W.C., Error analysis for the numerical evaluation of the diagonal forms of the scalar spherical addition theorem, (October 1997)
[42] Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, J. comput. phys., 135, 280, (1997) · Zbl 0898.70002
[43] Greengard, L.; Rokhlin, V., J. comput. phys., 73, 325, (1987)
[44] Lu, C.C.; Chew, W.C., A multilevel algorithm for solving a boundary integral equation of wave scattering, Micro. opt. tech. lett., 7, 466, (1994)
[45] Challacombe, M.; White, C.; Headgordon, M., Periodic boundary conditions and the fast multipole method, J. chem. phys., 107, 10131, (1997)
[46] Challacombe, M.; Schwegler, E.; White, C.; Johnson, B.; Gill, P.; Headgordon, M., Linear scaling computation of hf and hf/dft Fock matrices, ABS. papers am. chem. soc., 213, 57, (1997)
[47] McLaren, A.D., Optimal numerical integration on a sphere, Math. comput., 17, 361, (1963) · Zbl 0233.65016
[48] Michielssen, E.; Boag, A., Multilevel evaluation of electromagnetic fields for the rapid solution of scattering problems, Microwave opt. tech. lett., 7, 790, (1994)
[49] E. Michielssen, and, A. Boag, A multilevel matrix decomposition algorithm for analyzing scattering from large structures, in, 11th Annual Review of Progress in Applied Computational Electromagnetics, Monterey, CA, 1995, p, 614.
[50] Rao, S.M.; Wilton, D.R.; Glisson, A.W., Electromagnetic scattering by surfaces of arbitrary shape, IEEE trans. antennas propag., AP-30, 409, (1982)
[51] Rokhlin, V., Rapid solution of integral equations of scattering theory in two dimensions, J. comput. phys., 86, 414, (1990) · Zbl 0686.65079
[52] Rokhlin, V., Diagonal forms of translation operators for the Helmholtz equation in three dimensions, (March 1992)
[53] V. Rokhlin, Analysis-based fast numerical algorithms of applied mathematics, in, Proceedings of the International Congress of Mathematicians, Zürich, Switzerland, 1994. · Zbl 0839.65127
[54] Teng, S.H., Provably good partitioning and load balancing algorithms for a parallel adaptive n-body simulation, SIAM J. sci. comput., 19, 635, (1998) · Zbl 0907.68219
[55] Goh, S.K.; Sosa, C.P.; Stamant, A., A scalable divide-and-conquer algorithm combining coarse and fine-grain parallelization, Theor. chem. accounts, 99, 197, (1998)
[56] Song, J.M.; Chew, W.C., Multilevel fast-multipole algorithm for solving combined field integral equations of electromagnetic scattering, Microwave opt. tech. lett., 10, 14, (1995)
[57] Song, J.M.; Lu, C.-C.; Chew, W.C., Multilevel fast multipole algorithm for electromagnetic scattering by large complex objects, IEEE trans. antennas propag., 45, 1488, (1997)
[58] Song, J.M.; Lu, C.-C.; Chew, W.C.; Lee, S.W., Fast illinois solver code (fisc) solves problems of unprecendented size at the center for computational electromagnetics, university of illinois, (1997)
[59] Song, J.M.; Lu, C.C.; Chew, W.C.; Lee, S.W., Fast illinois solver code (fisc), IEEE antennas propag mag., 40, 27, (1998)
[60] Schlick, T.; Skeel, R.D.; Brunger, A.T.; Kalé, L.V.; Board, J.A.; Hermans, J.; Schulten, K., Algorithmic challenges in computational molecular biophysics, J. comput. phys., 151, 9, (1999) · Zbl 0935.92008
[61] Wagner, R.L.; Chew, W.C., A ray-progagation fast multipole algorithm, Microwave opt. tech. lett., 7, 435, (1994)
[62] Elliott, W.D.; Board, J.A., Fast Fourier-transform accelerated fast multipole algorithm, SIAM J. sci. comput., 17, 398, (1996) · Zbl 0855.70001
[63] White, C.A.; Johnson, B.G.; Gill, P.M.W.; Head-Gordon, M., The continuous fast multipole method, Chem. phys. lett., 230, 8, (1994)
[64] Yarvin, N.; Rokhlin, V., An improved fast multipole algorithm for potential fields on the line, SIAM J. numer. anal., 36, 629, (1999) · Zbl 0973.65106
[65] Yarvin, N.; Rokhlin, V., A generalized one-dimensional fast multipole method with application to filtering of spherical harmonics, J. comput. phys., 147, 594, (1998) · Zbl 0927.65138
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.