Repository logo

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

Journal Title

Journal ISSN

Volume Title


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.


Rights Access


hierarchical semi-separable structures
randomized sampling
fast multipole method
computational electromagnetics
method of moments


Associated Publications