An Adaptive Approximate Inverse-Based Preconditioner Combined with the Fast Multipole Method for Solving Dense Linear Systems in Electromagnetic Scattering
关键词:
An Adaptive Approximate Inverse-Based Preconditioner Combined with the Fast Multipole Method for Solving Dense Linear Systems in Electromagnetic Scattering摘要
We discuss preconditioning strategies for solving large Electric Field Integral Equation systems. We consider several algebraic preconditioners for solving the dense linear system arising from the Galerkin discretization of the pertinent integral equation.We show that approximate inverse methods based on Frobenius-norm minimization techniques can be very effective to reduce the number of iterations of Krylov subspace solvers for this problem class. We describe the implementation of the preconditioner within the Fast Multipole Algorithm and we illustrate how to reduce the construction cost by using static pattern selection strategies. Finally, we present deflating techniques based on low-rank matrix updates to enhance the robustness of the approximate inverse on tough problems. Experiments are reported on the numerical behavior of the proposed method on a set of realistic industrial problems.
##plugins.generic.usageStats.downloads##
参考
A.F. Peterson, S.L. Ray, and R. Mittra. Computa-
tional Methods for Electromagnetics. IEEE Press,
G. All ́eon, S. Amram, N. Durante, P. Homsi, D. Pog-
arieloff, and C. Farhat, ”‘Massively parallel process-
ing boosts the solution of industrial electromagnetic
problems: High performance out-of-core solution of
complex dense systems,”’ In M. Heath, V. Torc-
zon, G. Astfalk, P. E. Bj?rstad, A. H. Karp, C. H.
Koebel, V. Kumar, R. F. Lucas, L. T. Watson, and
Editors D. E. Womble, editors, Proceedings of the
Eighth SIAM Conference on Parallel. SIAM Book,
Philadelphia, Minneapolis, Minnesota, USA, 1997.
W. C. Chew and Y. M. Wang. A recursive T-
matrix approach for the solution of electromagnetic
scattering by many spheres. IEEE Transactions
on Antennas and Propagation, vol. 41, no. 12, pp.
–1639, 1993.
K. Chen. An analysis of sparse approximate in-
verse preconditioners for boundary integral equa-
tions. SIAM J. Matrix Analysis and Applications,
vol. 22, no. 3, pp. 1058–1078, 2001.
CARPENTIERI: ADAPTIVE APPROXIMATE INVERSE-BASED PRECONDITIONER WITH FMM SOLVER
K. Sertel and J. L. Volakis. Incomplete LU precon-
ditioner for FMM implementation. Micro. Opt. Tech.
Lett., vol. 26, no. 7, pp. 265–267, 2000.
A. Grama, V. Kumar, and A. Sameh. On n-body
simulations using message-passing parallel comput-
ers. In Sidney Karin, editor, Proceedings of the
SIAM Conference on Parallel Processing, San
Francisco, CA, USA, 1995.
S. A. Vavasis. Preconditioning for boundary integral
equations. SIAM J. Matrix Analysis and Applica-
tions, vol. 13, pp. 905–925, 1992.
J. Lee, C.-C. Lu, and J. Zhang. Incomplete LU
preconditioning for large scale dense complex linear
systems from electromagnetic wave scattering prob-
lems. J. Comp. Phys., vol. 185, pp. 158–175, 2003.
B. Carpentieri, I. S. Duff, L. Giraud, and M. Magolu
monga Made. Sparse symmetric preconditioners for
dense linear systems in electromagnetism. Tech-
nical Report TR/PA/01/35, CERFACS, Toulouse,
France, 2001. Also Technical Report RAL-TR-
-016. Preliminary version of the article accepted
for publication in Numerical Linear Algebra with
Applications.
T. Malas and L. G ̈urel. Incomplete LU precon-
ditioning with multilevel fast multipole algorithm
for electromagnetic scattering. SIAM J. Scientific
Computing, 2007. Accepted for publication.
G. All ́eon, M. Benzi, and L. Giraud. Sparse ap-
proximate inverse preconditioning for dense linear
systems arising in computational electromagnetics.
Numerical Algorithms, vol. 16, pp. 1–15, 1997.
A. R. Samant, E. Michielssen, and P. Saylor. Ap-
proximate inverse based preconditioners for 2D
dense matrix problems. Technical Report CCEM-
-96, University of Illinois, 1996.
J. Lee, C.-C. Lu, and J. Zhang. Sparse inverse pre-
conditioning of multilevel fast multipole algorithm
for hybrid integral equations in electromagnetics.
Technical Report 363-02, Department of Computer
Science, University of Kentucky, KY, 2002.
L. Greengard and V. Rokhlin. A fast algorithm
for particle simulations. Journal of Computational
Physics, vol. 73, pp. 325–348, 1987.
J. Song, C.-C. Lu, and W. C. Chew. Multilevel fast
multipole algorithm for electromagnetic scattering
by large complex objects. IEEE Transactions on
Antennas and Propagation, vol. 45, no. 10, pp.
–1493, 1997.
E. Darve. The fast multipole method: Numerical
implementation. J. Comp. Phys., vol. 160, no. 1,
pp. 195–240, 2000.
G. Sylvand. La M ́ethode Multipˆole Rapide en
Electromagn ́etisme : Performances, Parall ́elisation,
Applications. PhD thesis, Ecole Nationale des Ponts
et Chauss ́ees, 2002.
B. Carpentieri, I. S. Duff, and L. Giraud. Sparse pat-
tern selection strategies for robust Frobenius-norm
minimization preconditioners in electromagnetism.
Numerical Linear Algebra with Applications, vol. 7,
no. 7-8, pp. 667–685, 2000.
B. Carpentieri, I. S. Duff, and L. Giraud. A class of
spectral two-level preconditioners. SIAM J. Scientific
Computing, vol. 25, no. 2, pp. 749–765, 2003.
J. Erhel, K. Burrage, and B. Pohl. Restarted GMRES
preconditioned by deflation. J. Comput. Appl. Math.,
vol. 69, pp. 303–318, 1996.
Y. Saad. Projection and deflation methods for partial
pole assignment in linear state feedback. IEEE
Trans. Automat. Contr., vol. 33, no. 3, pp. 290–297,
R. Lehoucq, D. Sorensen, and P. Vu. ARPACK
User’s Guide: Solution of LargeScale Eigenvalue
Problems with Implicitly Restarted Arnoldi Methods.
Society for Industrial and Applied Mathematics,
Philadelphia, 1998.
