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.
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.
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.
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.
8. Sertel, K. and J. L. Volakis, "Incomplete LU preconditioner for FMM implementation," Micro. Opt. Tech. Lett., Vol. 26, No. 7, 265-267, 2000.
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.
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.
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.
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.
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.
14. Bebendorf, M., "Approximation of boundary element matrices," Numerische Mathematik, Vol. 86, No. 4, 565-589, 2000.
15. Bebendorf, M. and S. Rjasanov, "Adaptive low-rank approximation of collocation matrices," Computing, Vol. 70, No. 1, 1-24, 2003.
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.
18. Hackbush, W., "A sparse matrix arithmetic based on H-matrices," Computing, Vol. 62, No. 2, 89-108, 1999.
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.
20. Greengard, L. and W. Gropp, "A parallel version of the fast multipole method," Comput. Math. Appl., Vol. 20, 63-71, 1990.
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.
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.
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.
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.
28. Darve, E., "The fast multipole method: Numerical implementation," J. Comp. Phys., Vol. 160, No. 1, 195-240, 2000.
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.
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.
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.
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.
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.
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.
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.
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.
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.