Graduate Exam Abstract

Nabeel Moin

M.S. Final

August 4, 2017, 10:00 am - 12:00 pm

Engineering C101B (ECE Conference Room)

Randomized Hierarchical Semi-Separable Structures for Parallel Direct Double-Higher-Order Method of Moments

Abstract: 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 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(rN^2), 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(N) time, which we accomplish by means of the Fast Multipole Method (FMM) then the HSS construction time is reduced to O(r^2 N). This work presents the theory and implementation of the above method. Numerical validation will also be presented.

Adviser: Branislav Notaros
Co-Adviser: N/A
Non-ECE Member: Xinfeng Gao, Mechanical Engineering
Member 3: Ali Pezeshki, Electrical and Computer Engineering
Addional Members: N/A


Program of Study: