The Fast Direct Algorithm For Boundary Integral Equations In Two Dimendions

Nowadays, the rapid development of computer science leads to a large number of broad and deep researches on various electromagnetic numerical algorithms, making it possible to solve complex electromagnetic problems. The Method of Moments(MOM) is one of the classic numerical methods on the electromagnetic field, and the MOM algorithm tends to yield a dense N×N matrix. While the impedance matrix, resulting from discretization of integral equation, always possesses a hierarchical structure and large off-diagonal blocks which are rank-deficient. In order to reduce the amount of computational cost and storage of the dense matrix, the research on the rapid direct solution methods based on the MOM algorithm becomes an important emerging direction on computational electromagnetics area.First of all, the paper presents in detail a multi-level compression representation on the hierarchical structure for constructing the inversion of the matrix. The inversion scheme takes advantage of low rank characteristics of non-diagonal submatrices, and gets the inversion representation for approximation of the matrix with rank-deficient off-diagonal blocks. Recursive method is then demonstrated in employing this representation to obtain a multi-level decomposition method.Secondly, on the basis of the multi-level compression representation, a rapid direct inversion algorithm is illustrated for construction of a hierarchical factorization. The paper presents a formal description of the algorithm where the Gram-Schmidt orthogonalization method combined with Randomized algorithms to improve the traditional QR decomposition, and calculates the computational cost. The algorithm is entirely independent of the analytical origin of integral equation and can be easily integrated into the Method of Moments.At the end of the paper, a series of numerical examples are implemented to verify the performance and accuracy of the algorithm. The fast direct algorithm is purely based on matrix analysis theory, and can be easily incorporated into the MOM algorithm.