Sparse Inverse Preconditioning of Multilevel Fast Multipole
Algorithm for Hybrid Integral Equations in Electromagnetics

Jeonghwa Lee and Jun Zhang
Laboratory for High Performance Scientific Computing and Computer Simulation
Department of Computer Science
University of Kentucky
773 Anderson Hall
Lexington, KY 40506-0046, USA

Cai-Cheng Lu
Department of Electrical and Computer Engineering
University of Kentucky
Lexington, KY 40506-0046, USA


In computational electromagnetics, the multilevel fast multipole algorithm (MLFMA) is used to reduce the computational complexity of the matrix vector product operations. In iteratively solving the dense linear systems arising from discretized hybrid integral equations, the sparse approximate inverse (SAI) preconditioning technique is employed to accelerate the convergence rate of the Krylov iterations. We show that a good quality SAI preconditioner can be constructed by using the near part matrix numerically generated in the MLFMA. The main purpose of this study is to show that this class of the SAI preconditioners are effective with the MLFMA and can reduce the number of Krylov iterations substantially. Our experimental results indicate that the SAI preconditioned MLFMA maintains the computational complexity of the MLFMA, but converges a lot faster, thus effectively reduces the overall simulation time.

Key words: Krylov methods, sparse approximate inverse preconditioning, multilevel fast multipole algorithm, electromagnetic scattering

Mathematics Subject Classification: 65F10, 65R20, 65F30, 77C10

Download the PDF file lee-etal04a.pdf.

This paper has been published in IEEE Transactions on Antennas and Propagation, Vol. 52, No. 9, pp. 2277-2287 (2004).

Previously published as Technical Report 363-02, Department of Computer Science, University of Kentucky, Lexington, KY, 2002. Download the compressed postscript file, or the PDF file saifmm.pdf.gz.

The research work of Lee and Zhang was supported in part by the U.S. National Science Foundation under the grant CCR-9988165, CCR-0092532, and ACR-0202934, in part by the U.S. Department of Energy under grant DE-FG02-02ER45961, in part by the Japanese Research Organization for Information Science & Technology, and in part by the University of Kentucky Research Committee. Lu's research work was supported in part by the U.S. National Science Foundation under grant ECS-0093692, and in part by the U.S. Office of Naval Research under grant N00014-00-1-0605.