Study And Application Of Novel Preconditioning Technique And Fast Direct Solvers For Integral Equations Of Computational Electromegnetics

In modern communication/electronic devices design and research community, electromagnetic radiation and scattering analysis, electromagnetic compatibility investigation and optimization etc, progressively rely on computer simulations instead of actual measurement/experiments, on account of efficiency and low-cost. Among a variety of methods for computational electromagnetics(CEM) – Integral Equations method(also known as Method of Moments, Boundary Element Method) is well known for its good accuracy and built-in radiation boundary condition. Since first introduced by R. F. Harrington in his book in 1968, IE method had gradually become popular in 1980 s due to the improvement of computer technology and most importantly, the revolutionary progress on the development of fast algorithms. Famous fast algorithms like Fast Multipole Method(FMM), Multilevel Matrix Decomposition Algorithm(MLMDA), Adaptive Integral Method(AIM) and others boosted the computational capacity of IE method significantly.Generally, most of these fast algorithms function in the manner of accelerating the matrix-vector multiplication process, thus naturally they are often combined with iterative solvers to solve the corresponding linear system. For iterative solvers, slow-convergence problem occurs in several circumstances – target objects of complex geometries, electric large object with fine details and dense discretized Electrical Field Integral Equation(EFIE) etc. Traditionally, algebra-based preconditioning techniques like diagonal block preconditioning, incomplete LU preconditioning, sparse approximate inverse preconditioning and so on are used to accelerate the convergence. However, their efficacy is limited on tough cases.The main goal in this dissertation is proposing a number of new methods with novel techniques to substantially alleviate the slow-convergence issue and even avoid it, paving a robust, steady and fast path for the equation-solving processes. We investigate two general approaches to achieve our research goal – one is using novel preconditioning techniques for the iterative solvers to enhance the convergence; the other one is developing new fast direct solvers to bypass the convergence issue. There are five major contributions in this dissertation.1. Combine Calderón Multiplicative Preconditioner(CMP) with ACA algorithm to reduce the memory and computational cost of original CMP. The preconditioning technique based on Calderón identity is aimed at stabilizing electric field integral equation(EFIE). The improved preconditioner we proposed has adopted ACA algorithm in a multi-grade fashion to decrease the memory and computational cost during the preconditioning process.2. A novel multilevel sparse approximate inverse(ML-SAI) preconditioner is proposed to accelerate the convergence rate of Krylov iterations for solving 3D electromagnetic scattering by integral equation. This multilevel formatted preconditioning is derived from the hierarchical data structure of ?-matrices, which overcomes the construction restrict of conventional SAI preconditioner combined with popular fast algorithms like multilevel fast multipole algorithm(MLFMA). Numerical experiments have demonstrated that this proposed preconditioner can achieve fast convergence even for very complex structures.3. A hierarchical matrices(?-matrices) based fast direct solver is proposed to bypass the slow-convergence issue of iterative solvers. An MPI-OpenMP hybrid parallel fast ?-LU direct solvers are developed for dealing with multiple right-hand-side cases. Despite the inherently sequential nature of the??-LU operation, the solver exhibits excellent scaling properties up to several hundred processors. Numerical experiments are given to demonstrate the advantages and practicability of the fast direct solvers for arbitrary complex structures with low computational complexity.4. In order to extend the capacity of fast direct solver for electric large objects, we develop a new direct integral equation solver by that utilizes MLMDA/butterfly schemes for compressing the LU factors of a MoM matrix. When compared to its predecessor, the new solver has three important features of note.(i) The solver entirely bypasses the LR compression step of its predecessor and operates directly on butterfly-compressed blocks. The latter is achieved using new randomized schemes for rapidly adding and multiplying butterfly-compressed operators.(ii) The solver executes in parallel, using a hybrid MPI-OpenMP strategy to accelerate the hierarchical inverse/decomposition of the MoM matrix.(iii) The solver applies to large-scale 3D(as opposed to 2D) analysis and was implemented to invert a combined field(as opposed to an electric field) integral operator. The solver is capable of inverting MoM matrices that discretize combined field integral equations modeling scattering from electrically large structures involving millions of unknowns on a small cluster using just a few hours of CPU time.5. Investigate randomized schemes for butterfly reconstruction which are strongly hinged to the computational complexity of MLMDA-based direct solver. Randomized schemes rely on the information gathered by multiplying the sum or product of the two butterfly-compressed operators with random vectors to arrive at a compressed representation of the resulting operators. These randomized schemes can be regarded as far-reaching generalizations of randomized schemes for computing low-rank approximations of linear operators.