Randomized hierarchical semi-separable structures for parallel direct double-higher-order method of moments - Moin, Nabeel, author; Notaros, Branislav, advisor; Pezeshki, Ali, committee member; Gao, Xinfeng, committee member (Colorado State University. Libraries, 2017)
As technology grows more and more rapidly, the need for large-scale electromagnetics modelling arises. This includes software that can handle very large problems and simulate them quickly. The goal of this research is to introduce some randomized techniques to existing methods to increase the speed and efficiency of Computational Electromagnetics (CEM) simulations. A particularly effective existing method is the Surface Integral Equation (SIE) formulation of the Method of Moments (MoM) using Double Higher Order (DHO) modelling. The advantage of this method is that it can typically model geometries with fewer unknowns, but the disadvantage is that the system matrix is fully dense. In order to counter this drawback, we utilize Hierarchical Semi-separable Structures (HSS), a data-sparse representation that expresses the off-diagonal blocks of the matrix in terms of low rank approximations. This improves both the speed and memory efficiency of the DHO-MoM-SIE. Of the three steps of HSS (construction, factorization, and solving), the one with the most computational cost is construction, with a complexity of O(rN2), where N is the size of the matrix and r is maximum rank of the off-diagonal blocks. This step can be improved by constructing the HSS form with Randomized Sampling (RS). If a vector can be applied to the system matrix in O(N1.5) time, which we accomplish by means of the Fast Multipole Method (FMM) then the HSS construction time is reduced to O(r2 N1.5). This work presents the theory of the above methods. Numerical validation will also be presented.
Keywords: double-higher-order; hierarchical semi-separable structures; randomized sampling; fast multipole method; computational electromagnetics; method of moments