Research On Fast Method Of Moments Using Interpolatve Decomposition Of Low-rank Matrices

Interpolative Decomposition is an algorithm to reduce the storage requirement in Method of Moments(MoM)by compressing low-rank matrix blocks and to accelerate matrix-vector prod-uct calculation in an iterative solver.Using ID,each far-field matrix block can be expressed as a product of skeleton matrix and interpolation matrix,and skeleton basis functions are selected locally(skeletonization).With the help of octree data structure,we develop the single-level ID into a multi-level version(MLTD)which has a similar framework to MLFMA,further improv-ing the compression efficiency.Moreover,combined with Combined Field Integral Equation(CFIE),MLID is used to solve the electromagnetic scattering from a purely electric conduc-tor.However,The efficiency of skeletonization on coarser levels in MLID is much lower than that on finer levels.To overcome this weakness,we build a hybrid algorithm(MLID-FMA)in which MLFMA performs the skeleton-matrix-vector product calculation on coarser levels,and MLID is responsible for the skeleton-matrix-vector product calculation on finer levels.In the algorithm,input skeleton vectors obtained via MLID upward process on the intermediate level are used by MLFMA to perform the skeleton-matrix-vector product so that output skele-ton vectors concerning coarser levels are generated.Then,the task returns to MLID and the complete output vectors are obtained when MLID downward process finishes.In this disser-tation,the programming implementations of MLID-FMA are also studied.The fast algorithm differs from the original MoM mainly on the scheme for storing system matrix and the way to execute matrix-vector product.Owing to the dynamic polymorphism feature of C++ lan-guage,we declare the member functions related to matrix-vector product in the base class as pure virtual,which are later implemented in the subclasses.In this way,a general programming framework that abstracts MoM is obtained.The algorithms built or used in this dissertation are all developed under this framework.The main works are as follows:1.The contruction and implementations of MLID are proposed.Numerical examples arc given to verify the computational efficiency and numerical stability.2.A hybrid algorithm,namely MLID-FMA,which combines MLFMA with MLID,is pro-posed.In the hybrid,MLID undertakes the matrix-vector product calculation on lower levels while MLFMA performs the skeleton-matrix-vector product on higher levels.MLID-FMA has the advantages of both MLFMA and MLID.In addition,the parallel accelera-tion of MoM,MLFMA,MLID,and MLID-FMA is realized with OpenMP.3.Some strategies are put forward to improve the efficiency of the programs.A general programming framework for MoM and the fast algorithms is designed with the help of the dynamic polymorphism and the template mechanism of C++ language...