H-matrix based fast direct finite-element methods for large-scale electromagnetic analysis

In this work, we introduce a general mathematical framework called the hierarchical ([special characters omitted]) matrix framework to reduce the computational complexity of finite-element-based analysis of electromagnetic problems. In the mathematical literature, the existence of an [special characters omitted]-matrix approximation was only proved for elliptic partial differential equations that govern static phenomena. We provide the first proof for electrodynamic analysis. Based on the proof, we develop an [special characters omitted]-matrix-based direct finite-element solver of O( kNlogN) memory complexity and O( k2Nlog2N) time complexity for solving electromagnetic problems, where k is a small parameter that is adaptively determined based on accuracy requirements. Both inverse-based and LU-based direct solutions are developed. The LU-based solution is further accelerated by nested dissection. A comparison with the state-of-the-art direct finite element solver that employs the most advanced sparse matrix solution has shown clear advantages of the proposed direct solver. In addition, the proposed solver is applicable to arbitrarily-shaped three-dimensional structures and arbitrary inhomogeneity. To further reduce the computational complexity of the proposed methods, we develop a layered [special characters omitted]-inverse and a layered [special characters omitted]-LU to fully utilize the large zero blocks present in a finite-element-based system matrix. As a result, the storage complexity of the proposed methods is reduced from O(NlogN) to O(M logM), and the time complexity is reduced from O( Nlog2N) to O(Nlog 2M), where M is the number of unknowns in a single layer, which is in general orders of magnitude smaller than N. For periodic structures, we develop a layered H-matrix based reduction and cascading algorithm, which further reduces the time complexity to log 2(p)O(Mlog 2M), where p is the number of periods. To reduce the complexity down to linear, we take advantage of the layered and periodic properties along both transverse and layer growth directions, and develop an [special characters omitted]-matrix parametric cascading (HPC) based fast direct solver to solve a large-scale integrated circuit problem. The storage complexity is reduced to a single period storage of O(NsNx), where Ns is the number of surface unknowns along the transverse direction in one period and Nx is the number of surfaces in one period. Both Ns and Nx are constant numbers, despite the number of periods in both directions, therefore our proposed solver is able to solve arbitrarily large structures on a single machine with constant memory. We also provide the first theoretical study on the rank of the inverse finite-element matrix for 1-D, 2-D, and 3-D electrodynamic problems. We find that the rank of the inverse finite-element matrix is a constant, irrespective of electric size for 1-D electrodynamic problems. For 2-D electrodynamic problems, the rank grows very slowly with electric size as the square root of the logarithm of the electric size of the problem. For 3-D electrodynamic problems, the rank scales linearly with the electric size. The findings of this work are both theoretically proved and numerically verified. They are applicable to problems with inhomogeneous materials, arbitrarily shaped structures, and truncated with any kind of absorbing boundary condition. The findings on the rank of the inverse finite element matrix also lead to a theoretical proof on the fact that the rank of the interaction between two separated geometry blocks in a surface integral-equation based system scales linearly with the electric size of the block diameter instead of electric size square. (Abstract shortened by UMI.