volume | PIER Journals

Abstract

In this paper we describe an effective and inherently parallel approximate inverse preconditioner based on Frobenius-norm minimization that can be easily combined with the fast multipole method. We show the numerical and parallel scalability of the preconditioner for solving large-scale dense linear systems of equations arising from the discretization of boundary integral equations in electromagnetism. We introduce simple deflating strategies based on low-rank matrix updates that can enhance the robustness of the approximate inverse on tough problems. Finally, we illustrate how to improve the locality of the preconditioner by using nested iterative schemes with different levels of accuracy for the matrix-vector products. Experiments on a set of model problems representative of realistic scattering simulations in industry illustrate the potential of the proposed techniques for solving large-scale applications in electromagnetism.

1. Jin, K. S., T. I. Suh, S. H. Suk, B. C. Kim, and H. T. Kim, "Fast ray tracing using a space-division algorithm for rcs prediction," Journal of Electromagnetic Waves and Applications, Vol. 20, No. 1, 119-126, 2006.
doi:10.1163/156939306775777341 Google Scholar

2. Wang, Y. B., Y. M. Bo, and D. Ben, "Fast rcs computation with general asymptotic waveform evaluation," Journal of Electromagnetic Waves and Applications, Vol. 12, 1873-1884, 2007. Google Scholar

3. Wang, S., X. Guan, D. Wang, X. Ma, and Y. Su, "Fast calculation of wide-band responses of complex radar targets," Progress In Electromagnetics Research, Vol. 68, 185-196, 2007.
doi:10.2528/PIER06081702 Google Scholar

4. Sylvand, G., "La methode multipˆole rapide en electromagnetisme: Performances, parallelisation, applications," Ph.D. thesis, 2002. Google Scholar

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

6. 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

7. Song, J., 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, 1488-1493, 1997.
doi:10.1109/8.633855 Google Scholar

8. Sertel, K. and J. L. Volakis, "Incomplete LU preconditioner for FMM implementation," Micro. Opt. Tech. Lett., Vol. 26, No. 7, 265-267, 2000.
doi:10.1002/1098-2760(20000820)26:4<265::AID-MOP18>3.0.CO;2-O Google Scholar

9. Lee, J., C.-C. Lu, and J. Zhang, "Incomplete LU preconditioning for large scale dense complex linear systems from electromagnetic wave scattering problems," J. Comp. Phys., Vol. 185, 158-175, 2003.
doi:10.1016/S0021-9991(02)00052-9 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. Ewe, W.-B., L.-W. Li, Q. Wu, and M.-S. Leong, "Preconditioners for adaptive integral methods implementation," IEEE Transactions on Antennas and Propagation, Vol. 53, No. 7, 2346-2350, 2005.
doi:10.1109/TAP.2005.850760 Google Scholar

12. Malas, T. and L. Gurel, "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

13. Gould, N. I. M. and J. A. Scott, "Sparse approximate-inverse preconditioners using norm-minimization techniques," SIAM J. Scientific Computing, Vol. 19, No. 2, 605-625, 1998.
doi:10.1137/S1064827595288425 Google Scholar

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

15. Bebendorf, M. and S. Rjasanov, "Adaptive low-rank approximation of collocation matrices," Computing, Vol. 70, No. 1, 1-24, 2003.
doi:10.1007/s00607-002-1469-6 Google Scholar

16. Canning, F. X., "The impedance matrix localization (IML) method for moment-method calculations," IEEE Antennas and Propagation Magazine, 1990. Google Scholar

17. Greengard, L. and V. Rokhlin, "A fast algorithm for particle simulations," Journal of Computational Physics, Vol. 73, 325-348, 1987.
doi:10.1016/0021-9991(87)90140-9 Google Scholar

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

19. Hackbush, W. and Z. P. Nowak, "On the fast matrix multiplication in the boundary element method by panel clustering," Numerische Mathematik, Vol. 54, No. 4, 463-491, 1989.
doi:10.1007/BF01396324 Google Scholar

20. Greengard, L. and W. Gropp, "A parallel version of the fast multipole method," Comput. Math. Appl., Vol. 20, 63-71, 1990.
doi:10.1016/0898-1221(90)90349-O Google Scholar

21. 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

22. Bendali, A., "Approximation par elements finis de surface de problemes de diffraction des ondes electro-magnetiques," Ph.D. thesis, 1984. Google Scholar

23. Saad, Y., Iterative Methods for Sparse Linear Systems, PWS Publishing, 1996.

24. Grote, M. and T. Huckle, "Parallel preconditionings with sparse approximate inverses," SIAM J. Scientific Computing, Vol. 18, 838-853, 1997.
doi:10.1137/S1064827594276552 Google Scholar

25. Benzi, M., C. D. Meyer, and M. Touma, "A sparse approximate inverse preconditioner for the conjugate gradient method," SIAM J. Scientific Computing, Vol. 17, 1135-1149, 1996.
doi:10.1137/S1064827594271421 Google Scholar

26. Wang, P., Y. J. Xie, and R. Yang, "Novel pre-corrected multilevel fast multipole algorithm for electrical large radition problem," Journal of Electromagnetic Waves and Applications, Vol. 11, 1733-1743, 2007. Google Scholar

27. Pan, X. M. and X. Q. Sheng, "A highly efficient parallel approach of multi-level fast multipole algorithm," Journal of Electromagnetic Waves and Applications, Vol. 20, No. 8, 1081-1092, 2006.
doi:10.1163/156939306776930321 Google Scholar

28. Darve, E., "The fast multipole method: Numerical implementation," J. Comp. Phys., Vol. 160, No. 1, 195-240, 2000.
doi:10.1006/jcph.2000.6451 Google Scholar

29. Zhao, X. W., X.-J. Dang, Y. Zhang, and C.-H. Liang, "The multilevel fast multipole algorithm for emc analysis of multiple antennas on electrically large platforms," Progress In Electromagnetics Research, Vol. 69, 161-176, 2007.
doi:10.2528/PIER06121003 Google Scholar

30. Zhang, Y. J. and E. P. Li, "Fast multipole accelerated scattering matrix method for multiple scattering of a large number of cylinders," Progress In Electromagnetics Research, Vol. 72, 105-126, 2007.
doi:10.2528/PIER07030503 Google Scholar

31. Greenbaum, A., Iterative Methods for Solving Linear Systems, No. 17, Frontiers in Applied Mathematics, 1997.

32. Wilkinson, J. H., The Algebraic Eigenvalue Problem, Oxford University Press, 1965.

33. Trefethen, L. N. and III D. Bau, Numerical Linear Algebra, SIAM Book, 1997.

34. Lehoucq, R., 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, 1998.

35. Carpentieri, B., "A matrix-free two-grid preconditioner for boundary integral equations in electromagnetism," Computing, Vol. 77, No. 3, 275-296, 2006.
doi:10.1007/s00607-006-0161-7 Google Scholar

36. Fournier, L. and S. Lanteri, "Multiplicative and additive parallel multigrid algorithms for the acceleration of compressible flow computations on unstructured meshes," Applied Numerical Mathematics, Vol. 36, 401-426, 2001.
doi:10.1016/S0168-9274(00)00017-9 Google Scholar

37. Tuminaro, R. S., "A highly parallel multigrid-like method for the solution of the Euler equations," SIAM J. Scientific and Statistical Computing, Vol. 13, 88-100, 1992.
doi:10.1137/0913005 Google Scholar

38. Carpentieri, B., L. Giraud, and S. Gratton, "Additive and multiplicative two-level spectral preconditioning for general linear systems," SIAM J. Scientific Computing, 2006. Google Scholar

39. Saad, Y., "A flexible inner-outer preconditioned GMRES algorithm," SIAM J. Scientific and Statistical Computing, Vol. 14, 461-469, 1993.
doi:10.1137/0914028 Google Scholar

40. Van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, 2003.

41. Van der Vorst, H. A. and C. Vuik, "GMRESR: A family of nested GMRES methods," Numerical Linear Algebra with Applications, Vol. 1, 369-386, 1994.
doi:10.1002/nla.1680010404 Google Scholar

42. Grama, A., V. Kumar, and A. Sameh, "Parallel hierarchical solvers and preconditioners for boundary element methods," SIAM J. Scientific Computing, Vol. 20, No. 1, 337-358, 1999.
doi:10.1137/S1064827596313322 Google Scholar

43. Fraysse, V., L. Giraud, S. Gratton, and J. Langou, "A set of GMRES routines for real and complex arithmetics on high performance computers," Technical Report TR/PA/03/3, 2003. Google Scholar

Dr. Bruno Carpentieri