An Effective Sparse Approximate Inverse Preconditioner for the MLFMA Solution of the Volume-Surface Integral Equation


  • Jinbo Liu School of Information and Communication Engineering Communication University of China, Beijing, 100024, P. R. China
  • Zengrui Li School of Information and Communication Engineering Communication University of China, Beijing, 100024, P. R. China
  • Mang He School of Information and Electronics Beijing Institute of Technology, Beijing, 100081, P. R. China
  • Jianxun Su School of Information and Communication Engineering Communication University of China, Beijing, 100024, P. R. China


Method of moments (MoM), multilevel fast multipole algorithm (MLFMA), sparse approximate inverse preconditioner, volume-surface integral equation (VSIE)


In the framework of the multilevel fast multipole algorithm (MLFMA), effective construction of the sparse approximate inverse preconditioner (SAIP) for the volume-surface integral equation (VSIE) is discussed. A high quality SAIP for the entire VSIE matrix is constructed by using the sub-matrix of the nearfield interactions between the surface basis and testing functions arising from the surface integral equation alone. In addition, a simple sparse pattern selection scheme based on the geometrical information of nearby basis functions and octree regrouping strategy is proposed to enhance the efficiency of the SAIP. In contrast to the existing sparse pattern selection schemes, the proposed scheme utilizes the near-field matrix in the MLFMA more effectively with only one tuning parameter. Numerical results indicate that with the proposed scheme, both the memory usage and setup time for constructing an effective SAIP are significantly reduced without compromising the efficiency and robustness.


W. C. Chew, J. M. Jin, E. Michielssen, and J. M. Song, Fast and Efficient Algorithms in Computational Electromagnetics, Boston, MA: Artech House, 2001.

R. F. Harrington, Field Computation by Moment Methods, New York: MacMillan, 1968.

P. L. Rui and R. S. Chen, “An efficient sparse approximate inverse preconditioning for FMM implementation,” Microwave Opt. Technol. Lett., vol. 49, No. 7, pp. 1746-1750, July 2007.

B. Carpentieri, I. S. Duff, L. Giraud, and G. Sylvand, “Combining fast multipole techniques and an approximate inverse preconditioner for large electromagnetism calculations,” SIAM J. Sci. Comput., vol. 27, no. 3, pp. 774-792, 2005.

B. Carpentieri, I. S. Duff, and L. Giraud, “Sparse pattern selection strategies for robust Frobeniusnorm minimization preconditioners in electromagnetism,” Numer. Linear Algebra Appl., vol. 7, pp. 667-685, 2000.

J. Lee, J. Zhang, and C. C. Lu, “Sparse inverse preconditioning of multilevel fast multipole algorithm for hybrid integral equations in electromagnetics,” IEEE Trans. Antennas Propag., vol. 52, no. 9, pp. 2277-2287, Sept. 2004.

T. Malas, O. Ergul, and L. Gurel, “Sequential and parallel preconditioners for large-scale integralequation problems,” 2007 IEEE Computational Electromagnetics Workshop, pp. 35-43, Aug. 2007.

O. Ergul, T. Malas, and L. Gurel, “Solutions of large-scale electromagnetics problems using an iterative inner-outer scheme with ordinary and approximate multilevel fast multipole algorithms,” Progress in Electromagnetics Research, vol. 106, pp. 203-223, 2010.

S. M. Rao, D. R. Wilton, and A. W. Glisson, “Electromagnetic scattering by surfaces of arbitrary shape,” IEEE Trans. Antennas Propag., vol. 30, no. 5, pp. 409-418, May 1982.

D. H. Schaubert, D. R. Wilton, and A. W. Glisson, “A tetrahedral modeling method for electromagnetic scattering by arbitrarily shaped inhomogeneous dielectric bodies,” IEEE Trans. Antennas Propag., vol. 32, no. 1, pp. 77-85, Jan. 1984.

Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., Philadelphia: SIAM, 2003. [12] W. Joubert, “On the convergence behavior of the restarted GMRES algorithm for solving nonsymmetric linear systems,” Numerical Linear Algebra with Applications, vol. 1, no. 5, pp. 427- 447, 1994.

A. H. Baker, E. R. Jessup, and Tz. V. Kolev, “A simple strategy for varying the restart parameter in GMRES(m),” Journal of Computational and Applied Mathematics, vol. 230, no. 2, pp. 751-761, 2009.

S. Tao, “Block matrix preconditioner for the coupled volume-surface integral equation,” ACES Journal, vol. 29, no. 8, pp. 602-610, Aug. 2014.

J. Lee, J. Zhang, and C. C. Lu, “Incomplete LU preconditioning for large scale dense complex linear systems from electromagnetic wave scattering problems,” Journal of Computational Physics, vol. 185, pp. 158-175, Feb. 2003.

X. S. Li and M. Shao, “A supernodal approach to incomplete LU factorization with partial pivoting,” ACM Trans. Math. Software, vol. 37, no. 4, Article no. 43, Apr. 2011.

J. Liu, M. He, K. Zhang, B. Wang, and Q. Qiu, “Parallelization of the multilevel fast multipole algorithm by combined use of OpenMP and VALU hardware acceleration,” IEEE Trans. Antennas Propag., vol. 62, no. 7, pp. 3884-3889, July 2014.

A. C. Woo, H. T. G. Wang, M. J. Schuh, and M. L. Sanders, “EM programmer's notebook-benchmark radar targets for the validation of computational electromagnetics programs,” IEEE Antennas Propag. Magazine, vol. 35, no. 1, pp. 84-89, Feb. 1993.