An Incomplete Review of Fast Multipole Methods–from Static to Wideband–as Applied to Problems in Computational Electromagnetics
Keywords:
An Incomplete Review of Fast Multipole Methods–from Static to Wideband–as Applied to Problems in Computational ElectromagneticsAbstract
Fast multipole methods (FMM) and their immediate predecessors, tree codes, were developed in response to the need for solving Nbody problems that occur in applications as varied as biophysics, computational chemistry, astrophysics and electromagnetics. In all these areas, it is necessary to compute long range potentials of the form 1/R between a dense distribution of point charges, where R is the distance between any two charges. Often, repeated evaluation of these potentials is necessary. It is apparent that the cost of direct evaluation, which scales as O(N2) for N degrees of freedom, forms a fundamental bottleneck. FMM and tree methods ameliorate the cost associated with these computation; CPU times of these method scale as O(N). It stands to reason that FMM has had a seminal impact on a multitude of fields, so much so, that it was recognized as one of the top ten algorithms of the past century. A method to rapidly compute potentials of the form e-j κR/R soon followed. As the reader is aware, these potentials are the crux of integral equation based analysis tools in electromagnetics and the advent of these methods have transformed the face of computational electromagnetics. Consequently, the state of art of integral equation solvers has grown by leaps and bounds over the past decade. This paper attempts to present a detailed review of the state of art of FMM based methods that are used in computational electromagnetics, from the static to the high frequency regime.
Downloads
References
J. Jin, The Finite Element Method in
Electromagnetics. John wiley and sons,
J. H. Richmond, “Digital computer solutions
of the rigorous equations for scattering
problems,” Proceeding of the IEEE, vol. 53,
pp. 796–804,1965.
A. Appel, “An efficient program for many
body simulations,” SIAM J. Sci. Comput.,
vol. 6, pp. 85–103, 1985.
J. Barnes and P. Hut, “A hierarchical O(n log
n) force calculation algorithm,” Nature, vol.
, pp. 446–449, 1986.
V. Rokhlin, “Rapid solution of the integral
equations of classical potential theory,” J. of
Comp. Phy., vol. 60, pp. 187– 207, 1985.
L. Greengard and V. Rokhlin, “A fast
algorithm for particle simulations,” J. of
Comp. Phy., vol. 20, pp. 63–71, 1987.
L. Greengard, The Rapid Evaluation of
Potential Fields in Particle Systems.
Cambridge, MA: MIT Press, 1988.
L. Greengard and V. Rokhlin, “A new
version of the fast multipole method for the
Laplace equation in three dimensions,” Acta
Numerica, vol. 6, pp. 229–269, 1997.
F. Zhao, “An O(n) algorithm for three
dimensional n-body simulation,” Master’s
thesis, Massachusetts Institute of
Technology, 1987.
E. J. Weniger, “Addition theorems as
threedimensional Taylor expansions,”
International J. of Quantum Chemistry, vol.
, pp. 280–295, 2000.
P. B. Visscher and D. M. Apalkov, “Charge
based recursive fast multipole
micromagnetics,” Physica B: Physics of
Condensed Matter, vol. 343, pp. 184–188,
B. Shanker and H. Huang, “Accelerated
Cartesian expansions - a fast method for
computing of potentials of the form R-
ν for
all real
ν,” J. of Comp. Phy. , vol. 226, pp.
–753, 2007.
W. D. Elliott and J. A. Board, “Multipole
algorithms for molecular dynamics
simulation on high performance computers,”
Tech. Rep. TR95-003.html, Duke
University, 1995.
Y. Fu, K. J. Klimkowski, G. J. Rodin, E.
Berger, J. C. Browne, J. K. Singer, R. A. van
de Geijin, and K. S. Vemaganti, “A fast
solution method for three-dimensional
manyparticle problems of linear
elastosticity,” J. Numer. Methods Eng. , vol.
, pp. 1215–1229, 1998.
K. Yoshida, N. Nishimura, and S. Kobayashi,
“Application of fast multipole Galerkin
boundary integral equationmethod to
elastostatic crack problems in 3D,” Int. J.
Numer. Methods Eng. , vol. 50, pp. 525–527,
Y. H. Chen, W. C. Chew, and S. Zeroug,
“Fast multipole method as an efficient solver
for 2D elastic wavesurface integral
equations,” Computational mechanics , vol.
, pp. 495– 506, 1997.
Y. Fu and G. J. Rodin, “Fast solution method
for three-dimensional Stokesian
manyparticle problems,” Commun. Numer.
Meth. Eng., vol. 16, pp. 145–149, 2000.
K. Nabors and J. White, “Fastcap: A
multipole accelerated 2-D capacitance
extraction program,” IEEE Trans. Computer
Aided Design, vol. 10, pp. 1447–1459, 1991.
M. Kamon, M. J. Tsuk, and J. K. White,
“FASTHENRY: A multipole accelerated 3-
D inductance extraction program,” IEEE
Trans. Microwave Theory Tech., vol. 42, pp.
–1758, 1994.
F. Chen and D. Suter, “Using a fast multipole
method to accelerate spline evaluations,”
IEEE Computational Science and
Engineering, vol. 5, pp. 24–31, 1998.
J. R. Driscoll and J. D. M. Healy,
“Asymptotically fast algorithms for spherical
and related transforms ,” in 30 th annual
symposium on foundations of computer
science, (Research Triangle Park, NC), pp.
–349, IEEE Computer Society Press,
R. J. Chien and B. K. Alpert, “A fast
spherical filter with uniform resolution,” J.
of Comp. Phy., vol. 136, pp. 580–584, 1997.
L. Greengard and J. Strain, “A fast algorithm
for the evaluation of heat potentials,” Comm.
Pure Appl. Math., vol. 43, pp. 949–963,
J. Tausch, “A fast method for solving the
heat equation by layer potentials,” J. of
Comp. Phy. , vol. 224, no. 2, pp. 956–969,
VIKRAM, SHANKER: INCOMPLETE REVIEW OF FAST MULTIPOLE METHODS
J. R. Li and L. Greengard, “On the numerical
solution of the heat equation I: fast solvers
infree space,” J. of Comp. Phy., vol. 226, pp.
–1901, 2007.
V. Rokhlin, “Rapid solutions of integral
equations of scattering theory in two
dimensions,” J. of Comp. Phy., vol. 86, pp.
–439, 1990.
C. C. Lu and W. C. Chew, “Fast algorithm for
solving hybrid integral equations,” IEE
Proceedings H: Microwaves and Antennas ,
vol. 140, pp. 455–460, 1992.
N. Engheta, W. D. Murphy, V. Rokhlin, and
M. S. Vassiliou, “The fast multipole method
(FMM) for electromagnetic scattering
problems,” IEEE Trans. Antennas
Propagat., vol. 40, pp. 634–641, 1992.
V. Rokhlin, “Diagonal forms of translation
operators for the Helmholtz equation in three
dimensions,” Applied and Computational
Harmonic Analysis, vol. 1, pp. 82–93, 1993.
M. A. Epton and B. Dembart, “Multipole
translation theory for three dimensional
Laplace and Helmholtz equations,” SIAM J.
Sci. Compt., vol. 16, pp. 865–897, 1995.
W. C. Chew, S. Koc, J. M. Song, C. C. Lu,
and E. Michielssen, “A succint way to
diagonalized the translation matrix in three
dimensions,” IEEE AP-S Int. Symp ., pp.
–2075, 1997.
W. C. Chew, J. M. Jin, E. Michielssen, and J.
Song, eds., Fast and Efficient Algorithms in
Computational Electromagnetics . Artech
House Publishers, 2001.
N. Nishimura, “Fast multipole accelerated
boundary integral equation methods,” Appl.
Mech. Rev., vol. 55, pp. 299–324, 2002.
M. F. Gyure and M. A. Stalzer, “A
prescription for the multilevel Helmhotz
FMM,” IEEE Computational Science and
Engineering, vol. 5, no. 3, pp. 39–47, 1998.
S. Velamparambil, J. M. Song, W. C. Chew,
and G. K., “ScaleME: A portable scalable
multipole engine for electromagnetic and
acoustic integral equation solvers,” IEEE
AP-S Int. Symp., vol. 3, pp. 1774–1777,
S. Velamparambil, W. C. Chew, and J. Song,
“10 million unknowns: is it that big?,” IEEE
Trans. Antennas and Propagat., vol. 45, pp.
–58, 2003.
B. Hariharan, S. Aluru, and B. Shanker, “A
scalable parallel fast multipole method for
analysis of scattering from perfect
electrically conducting surfaces,” in
Supercomputing, ACM/IEEE 2002
Conference, pp. 42–42, 16-22 Nov. 2002.
B. Hariharan and S. Aluru, “Efficient parallel
algorithms and software for compressed
octrees with applications to hierarchical
methods,” Parallel Computing , vol. 31, pp.
– 331, 2005.
L. Gurel and O. Ergul, “Fast and accurate
solutions of extremely large integral-
equation problems discretised with tens of
millions of unknowns,” Electronics Lett .,
vol. 43, no. 9, pp. 499–500, April 26 2007.
O. Ergul and L. Gurel, “Hierarchical
parallelization strategy for multilevel fast
multipole algorithm in computational
electromagnetics,” Electronics Lett., vol. 44,
no. 1, pp. 3–5, January 3 2008.
L. Greengard, J. Huang, V. Rokhlin, and S.
Wandzura, “Accelerating fast multipole
methods for the Helmholtz equation at low
frequencies,” IEEE Computational Science
and Engineering, vol. 5, pp. 32–38, 1998.
B. Dembart and E. Yip, “The accuracy of
fast multipole methods for Maxwell’s
equations,” IEEE Computational Science
and Engineering, vol. 5, pp. 48–56, 1998.
J. S. Zhao and W. C. Chew, “MLFMA for
solving boundary equations of 2D
electromagnetic scattering from static to
electrodynamic,” Microw. and Opt. Tech.
Lett., vol. 20, pp. 306–311, 1999.
T. J. Cui and W. C. Chew, “Fast algorithm for
electromagnetic scattering by buried
conducting plates of large size,” IEEE Trans.
Antennas Propagat., vol. 47, no. 6, pp.
–1118, 1999.
J. S. Zhao and W. C. Chew,
“Threedimensional multilevel fast multipole
algorithm from static to electrodynamic,”
Microw. and Opt. Tech. Lett., vol. 26, pp.
–48, 2000.
B. Hu and W. C. Chew, “Fast inhomogenous
plane wave algorithm for scattering from
objects above the multilayered medium,”
IEEE Trans. Geoscience and Remote
Sensing, vol. 39, pp. 1028–1038, 2001.
ACES JOURNAL, VOL. 24, NO. 2, APRIL 2009
J. Sarvas, “Performing interpolation and
anterpolation entirely by fast Fourier
transform in the 3-D multilevel fast
multipole algorithm,” SIAM Journal on
Numerical Analysis, vol. 41, pp. 2180–2196,
E. Darve and P. Have, “Efficient fast
multipole method for low-frequency
scattering,” J. of Comp. Phy., vol. 197, pp.
– 363, January 2004.
H. Cheng, W. Y. Crutchfield, Z. Gimbutas,
L. F. Greengard, J. F. Ethridge, J. Huang, V.
Rokhlin, and N. Y. andJ. Zhao, “A wideband
fast multipole method for the Helmholtz
equation in three dimensions,” J. of Comp.
Phy, vol. 216, pp. 300–325, 2006.
H. Cheng, L. Greengard, and V. Rokhlin, “A
fast adaptive multipole algorithm in three
dimensions,” J. of Comp. Phy, vol. 155, pp.
–498, 1999.
S. Aluru, “Greengard’s N-body algorithm is
not order N,” SIAM J. Sci. Comput., vol. 17,
pp. 773–776, 1996.
M. S. Warren and J. K. Salmon, “A parallel
hashed oct-tree N-body algorithm,” in
Supercomputing ’93: Proceedings of the
ACM/IEEE conference on
Supercomputing, (New York, NY, USA), pp.
–21, ACM, 1993.
F. Sevilgen, S. Aluru, and N. Futamura,
“Parallel algorithms for tree accumulations,”
Journal of Parallel and Distributed
Computing, vol. 65, pp. 85–93, 2005.
J. T. J. White, “A multiscale method for fast
capacitance extraction,” in Proceedings of
the IEEE/ACM DAC, 1998.
S. Balasubramanian, L. N. Subramaniam,
and B. Shanker, “Fast integral equation
based analysis of magneto-static fields in
bulk nonlinear media,” IEEE Trans.
Magnetics, vol. 35, pp. 100–107, 2002.
V. Rokhlin and S. M. Wandzura, “The fast
multipole method for periodic structure,” in
IEEE AP-S Int. Symp., pp. 424–427, 1994.
J. A. Stratton, Electromagnetic theory .
McGraw-Hill, 1941.
M. Abramowitz and I. A. Stegun, Handbook
of Mathematical Functions with Formulas,
Graphs, and Mathematical Tables . New
York, NY: Dover Publications, Inc., 1972.
Z. Duan and R. Krasny, “An adaptive
treecode for computing nonbonded potential
energy in classical molecular systems,” J.
Comp. Chem., vol. 22, pp. 184–195, 2001.
I. Chowdhury and V. Jandhyala, “Single
level multipole expansions and operators for
potentials of the form r-
ν,” SIAM J. Sci.
Comput., vol. 26, pp. 930–943, 2005.
I. Chowdhury and V. Jandhyala, “Multilevel
multipole and local operators for potentials
of the form r-
ν,” Appl. Math. Lett ., vol. 18,
pp. 1184–1189, 2005.
E. W. Hobson, The Theory of Spherical and
Ellipsoidal Harmonics. Cambridge
University Press, 1931.
T. M. MacRobert, Spherical Harmonics .
Dover, 1947.
J. Applequist, “Traceless cartesian tensor
forms for spherical ha rmonic functions: new
theorems and applications to electrostatics of
dielectric media,” J. Phys. A: Math. Gen .,
vol. 22, pp. 4303–4330, 1989.
W. D. Elliott and J. A. Board, “Fast Fourier
transform accelerated fast multipole
algorithm,” SIAM J. Sci. Comput., vol. 17,
pp. 398– 415, 1996.
M. Vikram and B. Shanker, “Fast evaluation
of time domain fields in sub-wavelength
source/observer distributions using
accelerated Cartesian expansions (ace),” J. of
Comp. Phy, vol. 227, pp. 1007–1023, 2007.
B. Hu, W. C. Chew, E. Michielssen, and J.
Zhao, “An improved fast steepest descent
algorithm for the fast analysis of
twodimensional scattering problems,” Radio
Sci., vol. 34, pp. 759–772, 1999.
N. Yarvin and V. Rokhlin, “Generalized
Gaussian quadratures and singular value
decompositions of integral operators,” tech.
rep., Department of Computer Science , Yale
University 1996.
B. Hu, W. C. Chew, E. Michielssen, and J.
Zhano, “Fast inhomogeneous plane wave
algorithm for fast analysis of two-
dimensional scattering problems,” Radio
Sci., vol. 34, pp. 759–772, 1999.
R. Coifman, V. Rokhlin, and S. Wandzura,
“The fast multipole method for the wave
equation: A pedestrian prescription,” IEEE
Antennas Propagat. Mag., vol. 35, pp. 7–12,
June 1993.
VIKRAM, SHANKER: INCOMPLETE REVIEW OF FAST MULTIPOLE METHODS
V. Rokhlin, “Sparse diagonal forms for
translation operators for the Helmholtz
equation in two dimensions,” Tech. Rep.
YALEU/DCS/RR-1095, Yale University,
J. Rahola, “Diagonal forms of the translation
operators in the fast multipole algorithm for
scattering problems,” BIT Numerical
Mathematics, vol. 36, pp. 333–358, 1996.
A. D. McLaren, “Optimal numerical
integration on a sphere,” Mathematics of
Computation, vol. 17, pp. 361–383, 1963.
E. Darve, “The fast multipole method:
Numerical implementation,” J. of Comp. Phy
vol. 160, pp. 195–240, 2000.
J. Song and W. C. Chew, “Error analysis for
the truncation of multipole expansion of
vector Green’s functions,” IEEE Microwave
and Wireless Components lett., vol. 11, pp.
–313, 2001.
J. Y. Li, L. W. Li, B. L. Ooi, P. S. Kooi, and
M. S. Leong, “On the accuracy of the
addition theorem for a scalar green’s
function used in the FMM,” Micro. Opt.
Techn. Lett., vol. 31, pp. 439–442, 2001.
M. L. Hastriter, S. Ohnuki, and W. C. Chew,
“Error control of the translation operator in
D MLFMA,” Micro. Opt. Techn. Lett ., vol.
, pp. 184–188, 2003.
S. Koc, J. Song, and W. C. Chew, “Error
analysis for the numerical evaluation of the
diagonal forms of the scalar spherical
addition theorem,” SIAM J. Numer. Anal.,
vol. 36, no. 3, pp. 906–921, 1999.
M. Nilsson, “Stability of the high frequency
fast multipole method for helmholtz equation
in three dimensions,” BIT Numerical
Mathematics, vol. 44, pp. 773–791, 2004.
J. M. Song, C. C. Lu, W. C. Chew, and S. W.
Lee, “Fast illinois solver code (FISC),” IEEE
Antennas Propagat. Mag., vol. 40, pp. 27–
, 1998.
E. Darve, “The fast multipole method i: Error
analysis and asymptotic complexity,” SIAM
J. Numer. Anal., vol. 38, pp. 98–128, 2000.
C. C. Lu and W. C. Chew, “A multilevel
algorithm for solving boundary integral
wave scattering,” Micro. Opt. Techn. Lett.,
vol. 7, pp. 466–470, 1994.
J. M. Song and W. C. Chew, “Multilevel
fastmultipole algorithm for solving
combined field integral equations of
electromagnetic scattering,” Micro. Opt.
Techn. Lett., vol. 10, no. 1, pp. 14–19, 1995.
B. Dembart and E. Yip, “A 3D fast multipole
method for electromagnetics with multiple
levels,” in Proceedings of the 11th Annual
Conference on Applied Computational
Electromagnetics, vol. 1, (Monterey, CA),
pp. 621– 628, 1995.
T. Hrycak and V. Rokhlin, “An improved
fast multipole algorithm for potential fields,”
SIAM Journal on Scientific Computing , vol.
, pp. 1804–1826, 1998.
N. Yarvin and V. Rokhlin, “A generalized
D fast-multipole method, with applications
to filtering of spherical harmonics,” tech.
rep., Yale University, 1998.
B. Shanker, A. Ergin, M. Lu, and E.
Michielssen, “Fast analysis of transient
electromagnetic scattering phenomena using
the multilevel plane wave time domain
algorithm,” IEEE Trans. Antennas
Propagat., vol. 51, no. 3, pp. 628–641,
March 2003.
E. Michielssen and W. C. Chew, “Fast
steepest descent path algorithm for analyzing
scattering from two- dimensional objects,”
Radio Sci., vol. 31, pp. 1215–1224, 1996.
L. J. Jiang and W. C. Chew, “Low-frequency
fast inhomogeneous plane-wave algorithm
(LFFIPWA),” Micro. Opt. Techn. Lett ., vol.
, pp. 117–122, 2004.
R. L. Wagner and W. C. Chew, “A
raypropagation fast multipole algorithm,”
Micro. Opt. Techn. Lett ., vol. 7, pp. 435–
, 1994.
B. Shanker, S.-K. Han, and E. Michielssen,
“A fast multipole approach to computing
scattering from an inhomogeneous
bianisotropic cylindrical object using
Beltrami fields,” Radio Sci., vol. 33, pp. 17–
, 1998.
T. J. Cui and W. C. Chew, “Accurate
analysis of wire structures from very-low
frequency to microwave frequency,” IEEE
Trans. Antennas Propagat., vol. 50, pp. 301–
, 2002.
W. C. Chew, Waves and Fields in
Inhomogeneous Media. IEEE Press New
York, 1995.
ACES JOURNAL, VOL. 24, NO. 2, APRIL 2009
L. Xuan, A. Zhu, A. R. J., and S. D. Gedney,
“A broadband multilevel fast multipole
algorithm,” IEEE AP-S Int. Symp. And
USNC/URSI National Radio Science
Meeting, vol. 2, pp. 1195–1198, 2004.
H. Wallen and J. Sarvas, “Translation
procedures for broadband MLFMA,”
Progress in Electromagnetics Research , vol.
, pp. 47–78 2005.
H. Huang and B. Shanker, “A o(n) procedure
for evaluating the Yukawa potential and the
Ewald summation for peroidic systems,”
Submited to Journal of Computational
Physics (Tech. Report Available at
https://www.egr.msu.edu/ece/Technicalpaper
s/), 2007.
H. Huang and B. Shanker, “Accelerated
Cartesian expansion based method for
rapidly computing the shielded Coulomb
potential,” in URSI Int. Symp., 2007.
M. Vikram, H. Huang, and B. Shanker, “Fast
evaluation of fields from sub-wavelength
structures in frequencydomain,” in URSI Int.
Symp., 2007.
J. Carrier, L. Greengard, and V. Rokhlin, “A
fast adaptive multipole algorithm for particle
simulations,” SIAM J. Sci. Stat. Comput.,
vol. 9, pp. 669–686, 1988.
K. Nabors and J. White
“Multipoleaccelerated capacitance extraction
for 3-D structures with multilayer
dielectrics,” IEEE Tran. Circ. Syst., vol. 39,
pp. 946–954, 1992.
A. Adedoyin and P. Andrei, “3-D
magnetostatic using the fast multiple
method,” IEEE Trans. Magnetics, vol. 43,
no. 6, pp. 2914–2916, June 2007.
I. Mayergoyz, P. Andrei, and M. Dimian,
“Nonlinear magnetostatic calculations based
on fast multipole method,” IEEE Trans.
Magnetics, vol. 39, no. 3, pp. 1103–1106,
May 2003.
W. Hafla, A. Buchau, F. Groh, and W.
Rucker, “Efficient integral equation method
for the solution of 3-D magnetostatic
problems,” IEEE Trans. Magnetics , vol. 41,
no. 5, pp. 1408– 1411, May 2005.
Y. Takahashi, Y. Fujishima, and S. Wakao,
“Large-scale analysis of surface charge in
eddy-current problems by the fast multipole
method,” IEEE Trans. Magnetics, vol. 41,
no. 5, pp. 1700–1703, May 2005.
G. Rubinacci, A. Tamburrino, S. Ventre, and
F. Villone, “A fast 3-D multipole method for
eddy-current computation,” IEEE Trans.
Magnetics, vol. 40, no. 2, pp. 1290–1293,
March 2004.
C. Seberino and H. Bertram, “Concise,
efficient three-dimensional fast multipole
method for micromagnetics,” IEEE Trans.
Magnetics, vol. 37, no. 3, pp. 1078–1086,
May 2001.
D. Apalkov and P. Visscher, “Fast multipole
method for micromagnetic simulation of
periodic systems,” IEEE Trans. Magnetics,
vol. 39, no. 6, pp. 3478–3480, Nov. 2003.
J. M. Song, C. C. Lu, and W. C. Chew,
“MLFMA for electromagnetic scattering by
large complex objects,” IEEE Trans.
Antennas Propagat, vol. 45, pp. 1488–1493,
T. Eibert, “Some scattering results computed
by surface-integral-equation and by the
multilevel fast multipole method,” IEEE
Antennas Propagat. Mag., vol. 49, no. 2, pp.
–69, April 2007.
L. Hamilton, P. Macdonald, M. Stalzer, R.
Turley, J. Visher, and S. Wandzura, “3D
method of moments scattering computations
using the fast multipole method,” Antennas
and Propagation Society International
Symposium, 1994. AP-S. Digest, vol. 1, pp.
–438, 20-24 Jun 1994.
T. J. Cui, W. C. Chew, G. Chen, and J. Song,
“Efficient MLFMA, RPFMA, and FAFFA
algorithms for EM scattering by very large
structures,” IEEE Trans. Antennas
Propagat., vol. 52, no. 3, pp. 759–770,
March 2004.
K. Sertel and J. L. Volakis, “Effects of the
fast multipole method (FMM) parameters on
radar cross section computations,” IEEE AP-
S Int. Symp., pp. 624–627, 1999.
Z. Q. Zhang, Q. H. Liu, and X. M. Xu, “RCS
computation of large inhomogeneous objects
using fast integral equation solver,” IEEE
Trans. Antennas Propagat., vol. 51, pp. 613
, March 2003.
J. M. Song and W. C. Chew, “Fast multipole
method solution using parametric geometry,”
VIKRAM, SHANKER: INCOMPLETE REVIEW OF FAST MULTIPOLE METHODS
Micro. Opt. Tech. Lett., vol. 7, pp. 760–795,
K. Donepudi, J. M. Jin, and W. C. Chew, “A
higher order multilevel fast multipole
algorithm for scattering from mixed
conducting/dielectric bodies,” IEEE Trans.
Antennas Propagat., vol. 51, pp. 2814–2821,
K. Donepudi, J. Song, J. M. Jin, G. Kang,
and W. Chew, “A novel implementation of
multilevel fast multipole algorithm for
higher order Galerkin’s method,” IEEE
Trans. Antennas Propagat., vol. 48, no. 8,
pp. 1192–1197, Aug 2000.
J. Liu and J. M. Jin, “A novel hybridization
of higher order finite element and boundary
integral methods for electromagnetic
scattering and radiation problems,” IEEE
Trans. Antennas Propogat., vol. 49, no. 12,
pp. 1794–1806, Dec 2001.
H. Wallen, S. Jarvenpaa, P. Yla-Oijala, and J.
Sarvas, “Broadband Muller-MLFMA for
electromagnetic scattering by dielectric
objects,” IEEE Trans. Antennas Propagat .,
vol. 55, no. 5, pp. 1423–1430, May 2007.
V. Jandhyala, B. Shanker, E. Michielssen,
and W. Chew, “Fast algorithm for the
analysis of scattering by dielectric rough
surfaces,” J. of Opt. Society of America , vol.
, pp. 1877–1885, 1998.
X. Q. Sheng, J. J. M., J. M. Song, C. W. C.,
and C. C. Lu, “Solution of combined-field
integral equation using multilevel fast
multipole algorithm for scattering from
homogeneous bodies,” IEEE Antennas
Propagat. Mag., vol. 46, pp. 1718–1726,
C. C. Lu, “A fast algorithm based on volume
integral equation for analysis of arbitrarily
shaped dielectric radomes,” IEEE Trans.
Antennas Propogat., vol. 51, no. 3, pp. 606–
, March 2003.
J. Y. Li and L. W. Li, “Characterizing
scattering by 3d arbitrarily shaped
homogeneous dielectric objects using fast
multipole method,” IEEE Antennas Wireless
Propagati. Lett., vol. 3, pp. 1–4, 2004.
G. Kobidze, K. Aygun, and B. Shanker,
“Efficient integral equation based analysis of
scattering from PEC-anisotropic bodies,” in
Antennas and Propagation Society
International Symposium, 2004. IEEE, vol.
, pp. 3887– 3890Vol.4, 20-25 June 2004.
G. Kobidze and B. Shanker, “Integral
equation based analysis of scattering from 3-
d inhomogeneous anisotropic bodies,” IEEE
Trans. Antennas Propagat., vol. 52, pp.
–2658, Oct. 2004.
R. Wagner, J. Song, and W. Chew, “Monte
carlo simulation of electromagnetic
scattering from two-dimensional random
rough surfaces,” IEEE Trans. Antennas
Propagat., vol. 45, no. 2, pp. 235–245, 1997.
M. El-Shenawee, C. Rappaport, E. Miller,
and M. Silevitch, “Three-dimensional
subsurface analysis of electromagnetic
scattering from penetrable/PEC objects
buried under rough surfaces: use of the
steepest descent fast multipole method,”
IEEE Trans. Geoscience and Remote
Sensing, vol. 39, no. 6, pp. 1174–1182, Jun
V. Jandhyala, B. Shanker, E. Michielssen,
and W. Chew, “A combined steepest
descent-fast multipole algorithm for the
analysis of threedimensional scattering by
rough surfaces,” in Antennas and
Propagation Society International
Symposium, 1997. IEEE., 1997 Digest, vol.
, pp. 2308–2311vol.4, 13-18 July 1997.
V. Jandhyala, E. Michielssen, B. Shanker,
and W. Chew, “SDFMM-based fast analysis
of radiation and scattering from finite
microstrip structures,” in Antennas and
Propagation Society International
Symposium, 1998. IEEE, vol. 3, pp. 1530–
vol.3, 21-26 June 1998.
G. Hoyler and R. Unbehauen, “The fast
multipole method for EMC problem,”
Electrical Engineering, vol. 80, pp. 403–
, 1997.
H. Y. Chao, W. C. Chew, E. Michielssen,
and J. M. Song, “The multilevel fast
multipole algorithm for electromagnetic
compatibility analysis,” IEEE-EMC Int.
Symp., vol. 2, pp. 844– 847, 1999.
T. J. Cui, W. C. Chew, J. S. Zhao, and H. Y.
Chao, “Full-wave analysis of complicated
transmission-line circuits using wire
models,” IEEE Trans. Antennas Propagat.,
vol. 50, no. 10, pp. 1350–1360, 2002.
ACES JOURNAL, VOL. 24, NO. 2, APRIL 2009
Z. Z. Oo, L. Le-Wei, J. Y. Li, and E. P. Li,
“Analysis and design of reflector and horn
antennas using multilevel fast multipole
algorithms (MLFMA),” IEEE AP-S Int.
Symp., vol. 2, pp. 758–761, 22-27 June 2003.
J. Lord, S. Benham, and R. Mittra,
“Multilevel fast multipole for antenna
modelling,” Antennas and Propagation,
(ICAP 2003). Twelfth International
Conference on (Conf. Publ. No. 491), vol. 1,
pp. 308–311, 31 March- 3 April 2003.
H. Y. Chao, J. S. Zhao, and W. C. Chew,
“Application of curvilinear basis functions
and MLFMA for radiation and scattering
problems involving curved PEC structures,”
IEEE Trans. Antennas Propagat., vol. 51,
no. 2, pp. 331–336, Feb 2003.
K. Donepudi, J. M. Jin, S. Velamparambil, J.
M. Song, and W. C. Chew, “A higher-order
parallelized fast multipole algorithm for 3D
scattering,” IEEE Trans. Antennas
Propagat., vol. 49, pp. 1069–1078, 2001.
K. Donepudi, J. M. Song, J. M. Jin, G. Kang,
and W. C. Chew, “Point-based MLFMA for
Galerkin’s method,” IEEE Trans. Antennas
Propagat., vol. 48, pp. 1192–1197, 2000.
L. Gurel and M. Aksun, “Fast multipole
method in layered media: 2-D
electromagnetic scattering problems,” in
IEEE AP-S Int. Symp., pp. 1734–1737, 1996.
L. Gurel and M. Aksun, “Electromagnetic
scattering solution of conducting strips in
layered media using the fast multipole
method,” IEEE Microwave and Guided
Wave Letters, vol. 6, pp. 277, 1996.
J. M. Jin, The Finite Element Method in
Electromagnetics. New York: Wiley, 2002.
S. Bindiganavale and J. Volakis, “A hybrid
FEFMM technique for electromagnetic
scattering,” IEEE Trans. Antennas
Propagat., vol. 45, no. 1, pp. 180–181, Jan
N. Lu and J.-M. Jin, “Application of fast
multipole method to finite-element
boundaryintegral solution of scattering
problems,” IEEE Trans. Antennas
Propogat., vol. 44, no. 6, pp. 781–786, Jun
Z. Zhao, L. Li, J. Smith, and L. Carin,
“Analysis of scattering from very large
threedimensional rough surfaces using
MLFMM and ray-based analyses,” IEEE
Antennas Propagat. Mag., vol. 47, no. 3, pp.
– 30, June 2005.
P. L. Rui, R. S. Chen, D. X. Wang, and E.
Kai-Ning Yung, “A spectral multigrid
method combined with MLFMM for solving
electromagnetic wave scattering problems,”
IEEE Trans. Antennas Propagat, vol. 55, no.
, pp. 2571–2577, Sept. 2007.
T. Eibert, “Modeling and design of offset
parabolic reflector antennas using physical
optics and multilevel fast multipole method
accelerated method of moments,” Multitopic
Conference, 2006 . INMIC ’06. IEEE, pp.
–382, 23-24 Dec. 2006.
L. Gurel, A. Manyas, and O. Ergul,
“POMLFMA hybrid technique for the
solution of electromagnetic scattering
problems involving complex targets,”
Antennas and Propagation, EuCAP 2007.
The Second European Conference on, pp. 1–
, 11-16 Nov. 2007.
A. Tzoulis and T. Eibert, “Antenna modeling
with the hybrid finite element – boundary
integral - multilevel fast multipole – uniform
geometrical theory of diffraction method,”
nd International ITG Conference on
Antennas, INICA ’07 , pp. 91–95, 28-30
March 2007.
X. Yin, X. Zai, W. Hong, and X. Zhu, “A fast
algorithm based on MEI and FMM for field
prediction in urban mobile
communications,” IEEE AP-S Int. Symp.,
vol. 2, pp. 1384–1387, Aug 1999.
D. Pissoort, E. Michielssen, D. Ginste, and F.
Olyslager, “Fast-multipole analysis of
electromagnetic scattering by photonic
crystal slabs,” Journal of Lightwave
Technology, vol. 25, no. 9, pp. 2847–2863,
Sept. 2007.
D. Ginste, E. Michielssen, F. Olyslager, and
D. De Zutter, “An efficient perfectly
matched layer based multilevel fast
multipole algorithm for large planar
microwave structures,” IEEE Trans.
Antennas Propagat., vol. 54, no. 5, pp.
–1548, May 2006.
D. Pissoort, D. Ginste, and F. Olyslager,
“Including PML-based absorbing boundary
conditions in the MLFMA,” IEEE Antennas
VIKRAM, SHANKER: INCOMPLETE REVIEW OF FAST MULTIPOLE METHODS
and Wireless Propagat. Lett., vol. 4, pp.
–315, 2005.
V. Jandhyala, E. Michielssen, and R. Mittra,
“Multipole-accelerated capacitance
computation for 3-d structures in a stratified
dielectric medium using a closed form
green’s function,” Int. J. Microwave.
Millimeter Wave Comput. Aided Eng., vol. 5,
pp. 68–78, 1995.
L. Gurel and M. I. Aksun, “Electromagnetic
scttering solution of conducting strips in
layered media using the fast multipole
method,” IEEE Microwave Guided Wave
Letters, vol. 6, pp. 277–279, 1996.
P. A. MacDonald and T. Itoh, “Fast
simulation of microstrip structures using the
fast multipole method,” Int. J. Numerical
Modelling: Electron. Networks, Devices and
Fields, vol. 9, pp. 345–357, 1996.
J. Zhao, W. C. Chew, C. C. Lu, E.
Michielssen, and J. M. Song, “Thin-stratified
medium fastmultipole algorithm for solving
microstrip structures,” IEEE Trans.
Microwave Theory Tech., vol. 46, pp. 395–
, 1998.
V. Jandhyala, E. Michielssen, B. Shanker,
and W. C. Chew, “A fast algorithm for the
analysis of radiation and scattering from
arrays on finite substrates,” Micro. Opt.
Tech. Lett., vol. 23, pp. 306–310, 1999.
F. Ling, J. M. Song, and J. M. Jin,
“Multilevel fast multipole algorithm for
analysis of large scale microstripstructures,”
IEEE Microwave and Guided Wave Letts .,
vol. 9, pp. 508–510, 1999.
B. Hu and W. C. Chew, “Fast
inhomogeneous plane wave algorithm for
electromagnetic solutions in layered medium
structures-2D case,” Radio Sci. , vol. 35,
B. Hu and W. C. Chew, “Fast
inhomogeneous plane wave algorithm for
multilayered medium problems,” IEEE
Trans. Geoscience. Remote Sensing, vol. 39,
pp. 1028–1038, 2001.
N. Geng, A. Sullivan, and L. Carin,
“Multilevel fast-multipole algorithm for
scattering from conducting targets above or
embedded in a lossy half space,” IEEE
Trans. Geoscience Remote Sensing, vol. 38,
pp. 1567–1579, 2000.
N. Geng, A. Sullivan, and L. Carin, “Fast
multipole method analysis of scattering from
a three-dimensional target in a half-space
environment,” IEEE Trans. Antennas
Propagat., vol. 49, pp. 740–748, 2001.
Z. Liu, J. He, Y. Xie, A. Sullivan, and C. L.,
“Multi-level fast multipole algorithm for
general targets on a half-space interface,”
IEEE Trans. Antennas Propagat., vol. 50,
pp. 1838–1849, 2002.
Z. Liu, R. J. Adams, and C. L., “New
MLFMA formulation for closed pec targets
in the vicinity of a half space,” IEEE Trans.
Antennas Propagat., vol. 51, pp. 2822–2829,
X. Dong, Z. Liu, and L. Carin, “Volume and
surface MLFMA formulations for dielectric
targets in the presence of a half space,”
Radio Sci., vol. 39, 2004.
L. Li and L. Carin, “Multi-level fast
multipole method calibration of ray models
with application to wireless propagation,”
IEEE Trans. Antennas Propagat., vol. 52,
pp. 2794–2799, 2004.
M. A. Seville, Multilevel Multipole Free Fast
Algorithm for Elecgromagnetic Scattering
Problems in Layered Media. PhD thesis ,
University of Illinois at Urbana, 2006.
R. L. Wagner, Efficient computational
techniques for electromagnetic propagation
and scattering. PhD thesis , University of
Illinois at Urbana-Champaign, 1996.
R. L. Wagner, J. Song, and C. W. C., “Monte
Carlo simulation of electromagnetic
scattering from two-dimensional random
rough surfaces,” IEEE Trans. Antennas
Propogat., vol. 45, pp. 235–245, 1997.
V. Jandhyala, B. Shanker, E. Michielssen,
and W. C. Chew, “A combined steepest
descent fast multipole algorithm for the fast
analysis of three-dimensional scattering by
rough surfaces,” IEEE Trans. Geoscience
Remote Sensing, vol. 36, pp. 738–748, 1998.
V. Jandhyala, D. Sengupta, B. Shanker, E.
Michielssen, M. Feng, and G. Stillman,
“Two-dimensional rough surface couplers
for broadband quantum-well infrared
photodetectors,” Appl. Phys. Lett ., vol. 73,
pp. 3495–3497, 1998.
V. Jandhyala, D. Sengupta, B. Shanker, E.
Michielssen, M. Feng, and G. Stillman,
ACES JOURNAL, VOL. 24, NO. 2, APRIL 2009
“Efficient electromagnetic analysis of
twodimensional finite quasi-random gratings
of quantum well infrared photodetectors,” J.
Appl. Phys., vol. 83, pp. 3360–3363, 1998.
Z. Wang, Y. Yuan, and Q. Wu, “A parallel
multipole accelerated 3-D capacitance
simulator based on an improved model,”
IEEE Trans. Computer-Aided Design , vol.
, pp. 1441–1450, 1996.
J. Dull, K. Gallivan, J. M. Song, and W. C.
Chew, “Parallel fast multipole capacitance
solver,” IEEE AP-S Int. Symp ., vol. 3, pp.
–1769, 1998.
S. Velamparambil, J. E. Schutt-Aine, J. G.
Nickel, J. M. Song, and W. C. Chew,
“Solving large sclae electromagnetic
problems using a linux cluster and parallel
MLFMA,” IEEE APS Int. Symp., vol. 1, pp.
–639, 1999.
F. Wu, Y. Zhang, Z. Z. Oo, and E. Li,
“Parallel multilevel fast multipole method
for solving large-scale problems,” IEEE
Antennas Propagat. Mag., vol. 47, no. 4, pp.
– 118, Aug. 2005.
C. Waltz, K. Sertel, M. Carr, B. Usner, and J.
Volakis, “Massively parallel fast multipole
method solutions of large electromagnetic
scattering problems,” IEEE Trans. Antennas
Propagat., vol. 55, no. 6, pp. 1810–1816,
June 2007.
J. Lee, J. Zhang, and C.-C. Lu, “Sparse
inverse preconditioning of multilevel fast
multipole algorithm for hybrid integral
equations in electromagnetics,” IEEE Trans.
Antennas Propagat., vol. 52, no. 9, pp.
–2287, Sept. 2004.
P. Wang, Y. Xie, and R. Yang, “Analysis of
electrical large radiation problem with
precorrected multilevel fast multipole
algorithm,” IEEE Antennas and Wireless
Propagat. Lett., vol. 6, pp. 340–343, 2007.
P. L. Rui, R. S. Chen, D. X. Wang, and E. N.
Yung, “Spectral two-step preconditioning of
multilevel fast multipole algorithm for the
fast monostatic RCS calculation,” IEEE
Trans. Antennas Propogat., vol. 55, no. 8,
pp. 2268– 2275, Aug. 2007.
T. Malas and L. Gurel, “Incomplete LU
preconditioning strategies for MLFMA,”
IEEE AP-S Int. Symp., pp. 3921–3924, 2006.
O. Ergul, T. Malas, C. Yavuz, A. Unal, and
L. Gurel, “Computational analysis of
complicated metamaterial structures using
MLFMA and nested preconditioners,”
Antennas and Propagation, EuCAP 2007 .
The Second European Conference on, pp. 1–
, 11-16 Nov. 2007.
A. Ergin, B. Shanker, and E. Michielssen,
“The plane-wave time-domain algorithm for
the fast analysis of transient wave
phenomena,” IEEE Antennas Propagat.
Mag., , vol. 41, pp. 39–52, Aug. 1999.
B. Shanker, A. Ergin, K. Aygun, and E.
Michielssen, “Analysis of transient
electromagnetic scattering phenomena using
a twolevel plane wave time-domain
algorithm,” IEEE Trans. Antennas
Propagat., vol. 48, no. 4, pp. 510–523, 2000
