<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<sub>it</sub>N<sub>rhs</sub>)</i> with <i>N</i> being matrix size, <i>N<sub>it </sub></i>the number of iterations and <i>N<sub>rhs</sub></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<sup>3</sup>)</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<sup>2</sup>)</i>. Recently, an <i>H<sup>2</sup></i>-matrix based mathematical framework has been developed to obtain fast dense matrix algebra. However, existing linear-complexity <i>H<sup>2</sup></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<sup>2</sup></i> arithmetic, including matrix-matrix multiplication (MMP) without formatted multiplications, minimal-rank MMP, new accuracy controlled <i>H<sup>2</sup></i> factorization and inversion, new accuracy controlled <i>H<sup>2</sup></i> factorization and inversion with concurrent change of cluster bases, <i>H<sup>2</sup></i>-based direct sparse solver and new <i>HSS</i> recursive inverse with directly controlled accuracy. For constant-rank <i>H<sup>2</sup></i>-matrices, the proposed accuracy directly controlled <i>H<sup>2</sup></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<sup>2</sup></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<sup>2</sup></i> arithmetic and resulting fast direct solutions with explicitly controlled accuracy. In addition to electromagnetic analysis, the new <i>H<sup>2</sup></i> arithmetic developed in this work can also be applied to other disciplines, where fast and large-scale numerical solutions are being pursued. </div>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/9965408 |
| Date | 17 October 2019 |
| Creators | Miaomiao Ma (7485122) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/Accuracy_Explicitly_Controlled_H2-Matrix_Arithmetic_in_Linear_Complexity_and_Fast_Direct_Solutions_for_Large-Scale_Electromagnetic_Analysis/9965408 |
Page generated in 0.002 seconds