Accelerating the Multilevel Fast Multipole Method with Parallel Preconditioner for Large-Scale Scattering Problems
关键词:
Accelerating the Multilevel Fast Multipole Method with Parallel Preconditioner for Large-Scale Scattering Problems摘要
A novel parallel framework is proposed for the iterative solution of the multilevel fast multipole method (MLFMM). The inversion of the near-field impedance matrix is used as the preconditioner matrix to improve the convergence history of the ill-conditioned linear system formulated by electric field integral equation. In order to accelerate the inversion of the near field impedance matrix with huge number of unknowns, the parallel technique is used to construct the preconditioner matrix. Our numerical experiments reveal that with an efficiently parallelized MLFMM and the effective parallel preconditioner, we are able to solve problems with millions of unknowns in a few hours. Both the number of iteration steps and the overall simulation time can be saved significantly. For closed-surface problems analyzed by the combined-field integral equation, the number of iterations can also be reduced significantly by the proposed method. Numerical results are presented to demonstrate the accuracy and efficiency of the proposed method.
##plugins.generic.usageStats.downloads##
参考
S. Rao, D. Wilton, and A. Glisson,
“Electromagnetic Scattering by Surfaces of
Arbitrary Shape,” IEEE Trans. Antennas and
Propag., vol. 30, no. 3, pp. 409-418, May 1982.
K. A. Michalski and D. L. Zheng,
“Electromagnetic Scattering and Radiation by
Surfaces of Arbitrary Shape in Layered media, Part
I: Theory,” IEEE Trans. Antennas and Propag.,
vol. 38, no. 3, pp. 335-344, March 1990.
K. A. Michalski and D. L. Zheng,
“Electromagnetic Scattering and Radiation by
Surfaces of Arbitrary Shape in Layered Media, Part
II: Implementation and Results for Contiguous
Half-Spaces,” IEEE Trans. Antennas and Propag.,
vol. 38, no. 3, pp. 345-352, 1990.
D. Ding, J. Ge, and R. Chen, “Well-Conditioned
CFIE for Scattering from Dielectric Coated
Conducting Bodies above a Half-Space,” Applied
Computational Electromagnetic Society (ACES)
Journal, vol. 25, no. 11, pp. 936 - 946, 2010.
R. Coifman, V. Rokhlin, and S. M. Wandzura,
“The Fast Multipole Method for the Wave
Equation: A Pedestrian Prescription,” IEEE Trans.
Antennas Propag., vol. 35, no. 3, pp. 7-12, 1993.
J. M. Song, C. C. Lu., and W. C. Chew,
“Multilevel Fast Multipole Algorithm for
Electromagnetic Scattering by Large Complex
Objects,” IEEE Trans. Antennas and Propag., vol.
, no. 10, pp. 1488-1493, October 1997.
C. C. Lu and W. C. Chew, “A Multilevel
Algorithm for Solving Boundary Integral
Equations of Wave Scattering,” Micro. Opt. Tech.
Lett., vol. 7, pp. 466-470, July 1994.
J. M. Song and W. C. Chew, “Multilevel FastMultipole Algorithm for Solving Combined Field
Integral Equation of Electromagnetic Scattering,”
Micro. Opt. Tech. Lett., vol. 10, pp. 14-19,
September 1995.
M. M. Li, H. Chen, C. Li, R. S. Chen, and C. Ong,
“Hybrid UV/MLFMA Analysis of Scattering by
PEC Targets above a Lossy Half-Space,” Applied
Computational Electromagnetic Society (ACES)
Journal, vol. 26, no. 1, pp. 17-25, January 2011.
H. Zhao, J. Hu, and Z. Nie, “Parallelization of
MLFMA with Composite Load Partition Criteria
and Asynchronous Communication,” Applied
Computational Electromagnetic Society (ACES)
Journal, vol. 25, no. 2, pp. 167-173, 2010.
H. Fangjing, N. Zaiping, and H. Jun, “An Efficient
Parallel Multilevel Fast Multipole Algorithm for
Large-scale Scattering Problems,” Applied
Computational Electromagnetic Society (ACES)
Journal, vol. 25, no. 4, pp. 381-387, April 2010.
K. C. Donepudi, J. M. Jin et al, “A Higher Order
Parallelized Multilevel Fast Multipole Algorithm
for 3-D Scattering,” IEEE Trans. Antennas and
Propag., vol. 49, no. 7, pp. 1069-1078, July 2001.
W. Rankin and J. Board. “A Potable Distributed
Implementation of the Parallel Multipole Tree
Algorithm,” IEEE Symp. on High Performance
Distributed Computing, pp. 17-22, 1995.
X. M. Pan and X. Q. Sheng, “A Sophisticated
Parallel MLFMM for Scattering by Extremely
Large Targets,” IEEE Trans. Antennas and
Propag., vol. 50, no. 3, pp. 129-138, June 2008.
M. Grote and T. Huckle, “Parallel Preconditioning
with Sparse Approximate Inverses,” SIAM J. Sci.
Stat. Comput., vol. 18, pp. 838-853, 1997.
E. Chow, “A Priori Sparsity Patterns for Parallel
Sparse Approximate Inverse Preconditioners,”
SIAM J. Sci. Comput., vol. 21, pp. 1804-1822,
K. F. Tsang, R. S. Chen, M. Lei, and E. K. N.
Yung, “Application of the Preconditioned
Conjugate Gradient Algorithm to the Integral
Equations for Microwave Circuits,” Micro. Opt.
Tech. Lett., vol. 34 (4), pp. 266-270, 2002.
K. Wang, S. Kim, and J. Zhang, “A Comparative
Study on Dynamic and Static Scarcity Patterns in
Parallel Sparse Approximate Inverse
Preconditioning,” Journal of Mathematical
Modeling and Algorithms, vol. 2, no. 3, pp. 203-
, 2003.
Frequency
(GHz)
Unknowns No
preconditioner
NF_LU
preconditioner
35 34242 82 12
75 136968 76 15
5 547872 164 44
0 2191488 223 67
ACES JOURNAL, VOL. 26, NO. 10, OCTOBER 2011
Z. N. Jiang, Z. H. Fan, D. Z. Ding, R. S. Chen, and
K. W. Leung, “Preconditioned MDA-SVDMLFMA for Analysis of Multi-scale Problems,”
Applied Computational Electromagnetic Society
(ACES) Journal, vol. 25, no. 11, November 2010.
J. Lee, J. Zhang, and C. Lu, “Performance of
Preconditioned Krylov Iterative Methods for
Solving Hybrid Integral Equations in
Electromagnetics,” Applied Computational
Electromagnetic Society (ACES) Journal, vol. 18,
no. 3, pp. 54-61, November 2003.
