Fast Solvers and Preconditioning Methods in Computational Electromagnetics

Abstract

Method of Moments (MoM) is an integral equation based solver and is one of the most popular computational techniques to solve complex 3D Electromagnetic problems efficiently and accurately. Compared to the conventional differential equation solvers, MoM does not require a volumetric discretization of the entire bounding box containing the structure or imposes absorbing boundary condition or perfect match layer. However, due to Green's function interactions, the MoM matrix is dense leading to quadratic matrix fill time and cubic solve time complexity. As the scale and the complexity of the problem increases, matrix size increases with high storage memory and solve time requirement. Thus, to further expedite the solve time and decrease the storage requirement, fast solvers are extremely important. This thesis addresses the above problem by developing fast solvers and proposing a couple of novel preconditioning approaches for improving the solution speed of the fast solvers. The recent development of kernel-independent fast solvers has gained more popularity among the CEM community because of ease of their implementation. In this thesis, first, a brief overview of kernel dependent and kernel independent fast solvers is presented along with their parallelization. A new compression method is introduced based on the Adaptive Cross Approximation (ACA) sampling, where the pivot rows and columns can give a QR factorized orthogonal compressed matrices. These orthogonal matrices can be compressed further by using Interpolative Decomposition (ID) or can further be compressed by using Singular Value Decomposition (SVD) compression. The entire spectrum of fast solvers is highly dependent on the condition number of the matrices, specifically the spread of their eigenvalues. Hence, an ill-conditioned matrix jeopardizes the solution time and accuracy. This ill-conditioning mostly due to either geometry, meshing or the frequency of operation. Preconditioning the system of equations is the most efficient way to overcome ill-condition. Conventional preconditioners are either difficult to parallelize or lack linear scaling with problem size. In this thesis, we propose new preconditioners, which overcome the lacuna of the existing preconditioners. In the null-field preconditioner, near-field blocks are scaled to the diagonal blocks using the null-field method. The preconditioner is computed from all near-field blocks and selected far-field blocks in accordance with the null-field procedure. The final form of the preconditioner is block diagonal, therefore generates no additional fill-ins in its inverse and is also amenable to parallelization. A complexity analysis is presented to show the near-linear cost of preconditioner construction and usage in terms of computation time and memory. Numerical experiments with a sequential implementation demonstrate on an average 1.5-3x speed-up in the iterative solution time over Incomplete LU (ILUT) based preconditioners. Thus, giving a robust and stable preconditioner better than ILUT. The main drawback of the null-field method is the improper scaling of the near-field blocks. The next preconditioning method proposed in the thesis is based on the Schur’s complement method. The Schur’s complement method diagonalizes the near-field blocks to a block-diagonal form. The fill-in blocks generated in the process can be compressed efficiently and used for completely scaling the near-field blocks. Further fill-in reduction can be achieved by arranging the near-field blocks by using graph algorithms. Both these processes lead to a reduction in final matrix-vector product time in the iterative solver. Numerical experiments demonstrate a significant advantage over ILUT or recently published null-field based methods. In the case of multiport system or the problem with multiple Right Hand Side (RHS) iteration, the fast solver may turn out to be costly since each RHS may take different iteration thus taking more time to solve all RHSs so in such cases a direct solver is highly desirable. The complexity of the conventional direct solver is cubic so in this thesis, a fast direct solver based on the extended sparsification of FMM is proposed.