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

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.

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23. Saad, Y., Iterative Methods for Sparse Linear Systems, PWS Publishing, New York, 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

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

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.

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

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

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

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

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

32. Wilkinson, J. H., The Algebraic Eigenvalue Problem, Oxford University Press, Walton Street, Oxford OX2 6DP, UK, 1965.

33. Trefethen, L. N. and III D. Bau, Numerical Linear Algebra, SIAM Book, Philadelphia, 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, Philadelphia, 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

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

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

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

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

40. Van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, Cambridge, UK, 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

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

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.

Dr. Bruno Carpentieri