Accuracy Explicitly Controlled H2-Matrix Arithmetic in Linear Complexity and Fast Direct Solutions for Large-Scale Electromagnetic Analysis

<div>The design of advanced engineering systems generally results in large-scale numerical problems, which require efficient computational electromagnetic (CEM) solutions. Among existing CEM methods, iterative methods have been a popular choice since conventional direct solutions are computationally expensive. The optimal complexity of an iterative solver is <i>O(NN_itN_rhs)</i> with <i>N</i> being matrix size, <i>N_it</i>the number of iterations and <i>N_rhs</i> the number of right hand sides. How to invert or factorize a dense matrix or a sparse matrix of size <i>N</i> in <i>O(N)</i> (optimal) complexity with explicitly controlled accuracy has been a challenging research problem. For solving a dense matrix of size <i>N</i>, the computational complexity of a conventional direct solution is <i>O(N³)</i>; for solving a general sparse matrix arising from a 3-D EM analysis, the best computational complexity of a conventional direct solution is <i>O(N²)</i>. Recently, an <i>H²</i>-matrix based mathematical framework has been developed to obtain fast dense matrix algebra. However, existing linear-complexity <i>H²</i>-based matrix-matrix multiplication and matrix inversion lack an explicit accuracy control. If the accuracy is to be controlled, the inverse as well as the matrix-matrix multiplication algorithm must be completely changed, as the original formatted framework does not offer a mechanism to control the accuracy without increasing complexity.</div><div> </div><div>In this work, we develop a series of new accuracy controlled fast <i>H²</i> arithmetic, including matrix-matrix multiplication (MMP) without formatted multiplications, minimal-rank MMP, new accuracy controlled <i>H²</i> factorization and inversion, new accuracy controlled <i>H²</i> factorization and inversion with concurrent change of cluster bases, <i>H²</i>-based direct sparse solver and new <i>HSS</i> recursive inverse with directly controlled accuracy. For constant-rank <i>H²</i>-matrices, the proposed accuracy directly controlled <i>H²</i> arithmetic has a strict <i>O(N)</i> complexity in both time and memory. For rank that linearly grows with the electrical size, the complexity of the proposed <i>H²</i> arithmetic is <i>O(NlogN)</i> in factorization and inversion time, and <i>O(N)</i> in solution time and memory for solving volume IEs. Applications to large-scale interconnect extraction as well as large-scale scattering analysis, and comparisons with state-of-the-art solvers have demonstrated the clear advantages of the proposed new <i>H²</i> arithmetic and resulting fast direct solutions with explicitly controlled accuracy. In addition to electromagnetic analysis, the new <i>H²</i> arithmetic developed in this work can also be applied to other disciplines, where fast and large-scale numerical solutions are being pursued. </div>