volume | PIER Journals

Abstract

Boundary element discretizations of exterior Maxwell problems lead to dense complex non-Hermitian systems of linear equations that are difficult to solve from a linear algebra point of view. We show that the recently developed class of inverse-based multilevel incomplete LU factorization has very good potential to precondition these systems effectively. This family of algorithms can produce numerically stable factorizations and exploits efficiently the possible symmetry of the underlying integral formulation. The results are highlighted by calculating the radar-cross-section of a full aircraft, and by a numerical comparison against other standard preconditioners.

1. Amestoy, P., T. A. Davis, and I. S. Duff, "Algorithm 837:AMD, an approximate minimum degree ordering algorithm," ACM Transactions on Mathematical Software, Vol. 30, No. 3, 381-388, 2004.
doi:10.1145/1024074.1024081

2. Anderson, E., Z. Bai, C. Bischof, S. Blackford, J. Demmel,J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling,A. McKenney, and D. Sorensen, LAPACK Users' Guide, 3rd Edition, Society for Industrial and Applied Mathematics,Philadelphia, PA, 1999.
doi:10.1137/1.9780898719604

3. Andriulli, F. P., K. Cools, H. Bagci, F. Olyslager, A. Buffa,S. Christiansen, and E. Michielssen, "A multiplicative calderon preconditioner for the electric field integral equation," IEEE Transactions on Antennas and Propagation, Vol. 56, No. 8, 2398-2412, Aug. 2008.
doi:10.1109/TAP.2008.926788

4. Bebendorf, M., "Approximation of boundary element matrices," Numerische Mathematik, Vol. 86, No. 4, 565-589, 2000.
doi:10.1007/PL00005410

5. Bollhöfer, M. and Y. Saad, "Multilevel preconditioners constructed from inverse-based ILUs," SIAM J. Scientific Computing, Vol. 27, No. 5, 1627-1650, 2006.
doi:10.1137/040608374

6. Bollhöfer, M., Y. Saad, and O. Schenk, , ILUPACK --Preconditioning software package, Jun.2011, http://ilupack.tubs.de/.Release 2.4..
doi:10.1137/040608374

7. Bollhöfer, M., Marcus J. Grote, and O. Schenk., "Algebraic multilevel preconditioner for the Helmholtz equation in heterogeneous media," SIAM J. Scientific Computing, Vol. 31, No. 5, 3781-3805, 2009.
doi:10.1137/080725702

8. Bruno, O., T. Elling, R. Paffenroth, and C. Turc, "Electromagnetic integral equations requiring small numbers of krylov-subspace iterations," J. Comput. Phys., Vol. 228, 6169-6183, Sep. 2009.
doi:10.1016/j.jcp.2009.05.020

9. Carpentieri, B., "Algebraic preconditioners for the fast multipole method in electromagnetic scattering analysis from large structures: Trends and problems," Electronic Journal of Boundary Element, Vol. 7, No. 1, 13-49, 2009.

10. Carpentieri, B., I. S. Duff, L. Giraud, and M. Magolu Monga Made, "Sparse symmetric preconditioners for dense linear systems in electromagnetism," Numerical Linear Algebra with Applications,, Vol. 11, No. 8-9, 753-771, 2004.
doi:10.1002/nla.345

11. Carpentieri, B., I. S. Duff, L. Giraud, and G. Sylvand, "Combining fast multipole techniques and an approximate inverse preconditioner for large electromagnetism calculations," SIAM J. Scientific Computing, Vol. 27, No. 3, 774-792, 2005.
doi:10.1137/040603917

12. Carpentieri, B., Y.-F. Jing, and T.-Z. Huang, "The BiCOR and CORS algorithms for solving nonsymmetric linear systems SIAM J. Scientific Computing,", Vol. 33, No. 5, 3020-3036, 2011.
doi:10.1137/100794031

13. Chen, K., Matrix Preconditioning Techniques and Applications, Cambridge University Press, 2005.
doi:10.1017/CBO9780511543258

14. Chew, W. C. and K. F. Warnick, "On the spectrum of the electric field integral equation and the convergence of the moment method," Int J. Numerical Methods in Engineering, Vol. 51, 475-489, 2001.

15. Cui, Z., Y. Han, and M. Li, "Solution of CFIE-JMCFIE using parallel MoM for scattering by dielectrically coated conducting bodies," Journal of Electromagnetic Waves and Applications, Vol. 25, No. 2-3, 211-222, 2011.
doi:10.1163/156939311794362876

16. Cuthill, E. and J. McKee, "Reducing the bandwidth of sparse symmetric matrices," Proc. 24th National Conference of the Association for Computing Machinery, 157-172, Brandon Press,New Jersey, 1969.

17. Duff, I. S. and J. Koster, "The design and use of algorithms for permuting large entries to the diagonal of sparse matrices," SIAM J. Matrix Analysis and Applications, Vol. 20, No. 4, 889-901, 1999.
doi:10.1137/S0895479897317661

18. Duff, I. S. and S. Pralet, "Strategies for scaling and pivoting for sparse symmetric indefinite problems," SIAM J. Matrix Analysis and Applications, Vol. 27, No. 2, 313-340, 2005.
doi:10.1137/04061043X

19. Durdos, R., "Krylov solvers for large symmetric dense complex linear systems in electromagnetism: Some numerical experiments," Working Notes WN/PA/02/97, CERFACS, Toulouse, France, 2002.

20. Ergül, Ö and L. Gürel, "Effcient solutions of metamaterial problems using a low-frequency Multilevel Fast Multipole Algorithm," Progress In Electromagnetics Research, Vol. 108, 81-99, 2010.
doi:10.2528/PIER10071104

21. Ergül, Ö, T. Malas, and L. Gürel, "Solutions of largescale electromagnetics problems using an iterative inner-outer scheme with ordinary and approximate Multilevel Fast Multipole Algorithms," Progress In Electromagnetics Research, Vol. 106, 203-223, 2010.
doi:10.2528/PIER10061711

22. Freund, R. W., "Conjugate gradient-type methods for linear systems with complex symmetric coeffcient matrices," SIAM J. Scientific and Statistical Computing,, Vol. 13, No. 1, 425-448, 1992.
doi:10.1137/0913023

23. George, J. and J. W. H. Liu, "The evolution of the minimum degree ordering algorithm," SIAM Review, Vol. 31, 1-19, 1989.
doi:10.1137/1031001

24. Gürel, L. and T. Malas, "Iterative near-field preconditioner for the Multilevel Fast Multipole Algorithm," SIAM J. Scientific Computing, Vol. 32, 1929-1949, 2010.
doi:10.1137/09076101X

25. Hackbush, W., "A sparse matrix arithmetic based on H-matrices," Computing, Vol. 62, No. 2, 89-108, 1999.
doi:10.1007/s006070050015

26. Jing, Y.-F., B. Carpentieri, and T.-Z. Huang, "Experiments with Lanczos biconjugate a-orthonormalization methods for MoM discretizations of Maxwell's equations," Progress In Electromagnetics Research, Vol. 99, 427-451, 2009.
doi:10.2528/PIER09101901

27. Karypis, G. and V. Kumar, "Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices version 4.0,", http://glaros.dtc.umn.edu/gkhome/views/metis, University of Minnesota, Department of Computer Science/Army HPC Research Center Minneapolis, MN 55455, 1998.

28. Lai, B., H.-B. Yuan, and C.-H. Liang, "Analysis of Nurbs surfaces modeled geometries with higher-order MoM based AIM," Journal of Electromagnetic Waves and Applications, Vol. 25, No. 5-6, 683-691, 2011.
doi:10.1163/156939311794827285

29. Lim, H. and N.-H. Myung, "A novel hybrid Aipo-MoM technique for jet engine modulation analysis," Progress In Electromagnetics Research, Vol. 104, 85-97, 2010.
doi:10.2528/PIER10033103

30. Malas, T. and L. Gürel, "Incomplete LU preconditioning with Multilevel Fast Multipole Algorithm for electromagnetic scattering," SIAM J. Scientific Computing, Vol. 29, No. 4, 1476-1494, 2007.
doi:10.1137/060659107

31. Pan, X.-M., L. Cai, and X.-Q. Sheng, "An effcient high order Multilevel Fast Multipole Algorithm for electromagnetic scattering analysis," Progress In Electromagnetics Research, Vol. 126, 85-100, 2012.
doi:10.2528/PIER12020203

32. Pan, X.-M., W.-C. Pi, and X.-Q. Sheng, "On OpenMP parallelization of the Multilevel Fast Multipole Algorithm," Progress In Electromagnetics Research, Vol. 112, 199-213, 2011.

33. Pan, X. M. and X. Q. Sheng, "An effcient parallel SAI preconditioner for multilevel fast multipole algorithm for scattering by extremely large complex targets," Int. Conf. Microw. Millim. Wave. Tech., 407-410, 2009.

34. Rao, S. M., D. R. Wilton, and A. W. Glisson, "Electromagnetic scattering by surfaces of arbitrary shape," IEEE Trans. on Antennas and Propagat., Vol. 30, 409-418, 1982.
doi:10.1109/TAP.1982.1142818

35. Rokhlin, V., "Rapid solution of integral equations of scattering theory in two dimensions," J. Comp. Phys., Vol. 86, No. 2, 414-439, 1990.
doi:10.1016/0021-9991(90)90107-C

36. Saad, Y., Iterative Methods for Sparse Linear Systems, 2nd Edition, SIAM Publications, 2003.
doi:10.1137/1.9780898718003

37. Saad, Y. and M. H. Schultz, "GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems," SIAM J. Scientific and Statistical Computing, Vol. 7, 856-869, 1986.

38. Su, J., X.-W. Xu, and B. Hu, "Hybrid PMM-MoM method for the analysis of finite periodic structures," Journal of Electromagnetic Waves and Applications, Vol. 25, No. 2-3, 267-282, 2011.
doi:10.1163/156939311794362867

39. Wang, W. and N. Nishimura, "Calculation of shape derivatives with periodic Fast Multipole Method with application to shape optimization of metamaterials," Progress In Electromagnetics Research, Vol. 127, 49-64, 2012.
doi:10.2528/PIER12013109

40. Yan, S., J.-M. Jin, and Z. Nie, "Calderon preconditioning techniques for integral equation based methods," URSI Interna tional Symposium on Electromagnetic Theory (EMTS), 130-133, Aug. 2010.
doi:10.1109/URSI-EMTS.2010.5637125

41. Zhao, X.-W., Y. Zhang, H.-W. Zhang, D. Garcia-Donoro, S.-W. Ting, T. K. Sarkar, and C.-H. Liang, "Parallel MoM-PO method with out-of-core technique for analysis of complex arrays on electrically large platforms," Progress In Electromagnetics Research, Vol. 108, 1-21, 2010.
doi:10.2528/PIER10072108

Dr. Bruno Carpentieri

Dr. Matthias Bollhöfer