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 Google Scholar

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 Google Scholar

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

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

Dr. Bruno Carpentieri

Dr. Matthias Bollhöfer