ACCELERATING THE MULTILEVEL FAST MULTIPOLE ALGORITHM WITH THE SPARSE-APPROXIMATE-INVERSE (SAI) PRECONDITIONING

摘要

With the help of the multilevel fast multipole algorithm, integral-equation methods can be used to solve real-life electromagnetics problems both accurately and efficiently. Increasing problem dimensions, on the other hand, necessitate effective parallel preconditioners with low setup costs. In this paper, we consider sparse approximate inverses generated from the sparse near-field part of the dense coefficient matrix. In particular, we analyze pattern selection strategies that can make efficient use of the block structure of the near-field matrix, and we propose a load-balancing method to obtain high scalability during the setup. We also present some implementation details, which reduce the computational cost of the setup phase. In conclusion, for the open-surface problems that are modeled by the electric-field integral equation, we have been able to solve ill-conditioned linear systems involving millions of unknowns with moderate computational requirements. For closed-surface problems that can be modeled by the combined-field integral equation, we reduce the solution times significantly compared to the commonly used block-diagonal preconditioner.