Research On Divide And Conquer Algorithms For Complex Electromagnetic Problems

Nowadays,electromagnetic(EM)simulation has become a fundamental tool for scientific research,and has become a bridge between theory and practice.Fast accurate convenient solution of complex electromagnetic problems has extremely wide applications in different area of science and engineering.However,with the rapid development of technology,EM problems is getting more and more complicated,and the scale of these problems is increasing day by day.Current EM computation methods are still far from enough to meet the increasing requirements in science and engineering.Many practical EM problems are becoming more difficult than ever before and generally involve electrically large size,complex geometric structure,complex material properties,complex electromagnetic environment,and so on.There is an urgent need to develop new forces of EM solution methods to deal with these more challenging problems.This dissertation will face up to the above chanllenges.Specifically,this study will focus on the complex electrically large multiscale electromagnetic problems and conduct research on related divide and conquer(DAC)algorithms.With numerous practical applications as the general background,this study will pay more attentions to the common foundations of different concrete scenarios and will concentrate on developing fundamental divide and conquer algorithms.By investigating the potential connections between “Wave physics” and “Divide and Conquer Philosophy”,this study tries to upgrade several key aspects of the DAC algorithms for complex EM problems,including the computational complexity for complex targets,the numerical stability for electrically large sizes,the computational efficiency for multiscale situations,the algorithm usability for practical problems,etc.The main contributions of this dissertation are summarized as follows:1.A Multi-Directional Multi-Level Fast Complex Space Multi-Pole Algorithm(MDML-FCSMA)for complex target is proposed.Generally speaking,the proposed method,which combines the basic ideas of the Multi-Level Fast Multi-Pole Algorithm(MLFMA)and the Multi-Level Matrix Decomposition Method(MLMDA),demonstrates a systematic approach to truly incorporate high frequency ray physics into the algorithm framework of the MLFMA.Concretely,the proposed method is established by generalizing different key modules of the MLFMA to different extent.First,based on the directional multilevel structure and the Gaussian beam translator,a translational invariance property which is the core of the whole algorithm is revealed by setting up certain functional relation between spatial-spectral domains and electromagnetic-geometric quantities.Then,a necessary strategy of separating the interpolation points and the quadrature points is adopted,resulting in numerical integration on the sphere cap within the local coordinate and local interpolation on the unit sphere within the global coordinate.Finally,a “translation-driven” setup procedure and a “radiation pattern localization”execution procedure are achieved.Theoretical analysis and numerical experiments demonstrate that,different from the MLFMA,for 1D-enlongated,2D-suface-like,3D-volume-type electrically large objects,the proposed method shows stable quasi-linear computational complexity and good error controllability in all cases.2.A Multi-Directional Multi-Level Fast Inhomogeneous Plane Wave Algorithm(MDML-FIPWA)for electrically large target is proposed.From the perspective of algorithm effectiveness,previous Multi-Level Fast Inhomogeneous Plane Wave Algorithm(ML-FIPWA)has the inevitable problem of numerical overflow when calculating electrically large objects,thus being numerically unstable.In contrast,the proposed method possesses excellent numerical stability and can solve electrically large problems effectively.From the perspective of the essence of the problem,by analyzing the magnitudes of several constituents of the expansion of the Green's function under different multilevel structures and corresponding far field conditions,a key exponential factor which dominates the numerical stability is illuminated.Accordingly,the deeper reason for the instability of previous ML-FIPWA is clarified,and the principle of maintaining the stability of the proposed MDML-FIPWA is also made clear.Besides,different from previous ML-FIPWA,the proposed method possesses stable quasi-linear computational complexity when handling objects with dramatic different geometric features.3.A Multi-Directional Multi-Level Fast Homotopic Multi-Pole Algorithm based on Perfectly Matched Layers(MDMLMP-PMLHA)is proposed.The whole algorithm starts with the rectangular waveguide filled with the perfectly matched layers(PML).Then,by using the equivalence relationship between mode representation and ray representation,together with the interpolation and extrapolation of the radiation pattern functions,a fast algorithm of “Butterfly Multi-Pole” type is ultimately established.The construction of the whole algorithm does not depend on any numerical quadrature discretization,and only involves basic truncation of infinite series together with simple exchange of the order of summations.Theoretic analysis and numerical experiments demonstrate that the proposed method possesses stable computational complexity and good error controllability for complex electrically large objects.Besides,by uncovering the intrinsic mode-homotopic properties,a unique perspective for understanding multi-pole type algorithms is proposed.Meanwhile,the proposed algorithm also establishes an interesting and concrete connection between several classical models and classical concepts in microwave engineering.4.A hybrid method for efficient analysis of electromagnetic multiscale problems based on the pre-split Green's function(MS-PSG-FFT-ACA)is proposed.In this scheme,the Green's function is a prior split into two parts.Then,a hybrid algorithm using both the fast Fourier transforms(FFT)and the adaptive cross approximation(ACA)is established.Compared with previous methods which only employ the FFT for acceleration,the proposed method can maintain low memory consumption in multiscale cases without compromising time cost.Besides,different from previous hybrid scheme based on the numerical pre-corrections,the proposed method can construct auxiliary Cartesian grids and octree grouping independently,due to the merit of the pre-splitting realized at analytical level.Thus,the process of establishing the proposed method is far more concise and straightforward.5.An integral equation black box overlapping domain decomposition method(IE-ODDM-BB)for complex electrically large objects is proposed.Specifically,based on the idea of “Element and Union”,a geometry-blind domain decomposition scheme is introduced.Meanwhile,a sequence acceleration strategy is also introduced so as to greatly improve the robustness of the iterative solution process of the algorithm.Different from previous integral equation overlapping domain decomposition method(IE-ODDM),the proposed method only needs the mesh used for the method of moment(Mo M)without any domain partitioning information,and the establishment of the whole algorithm does not depend on the geometric modeling procedures(CAD)of the object.Accordingly,the proposed DDM can be plugged into current EM simulation software in a straightforward manner.Besides,for ordinary users,the proposed DDM can execute partitioning and solving process automatically without any user interference.Numerical experiments demonstrate that,compared with typical CG-MLFMA(without DDM),the proposed IE-ODDM-BB-MLFMA can solve complex electrically large scattering problems with much lower memory requirement.6.An overlapping domain decomposition method based on the Calderon preconditioned combined field integral equation(CP-CFIE-ODDM)is proposed.Previous versions of integral overlapping domain decomposition methods(IE-ODDMs)are all constructed based on the integral equations formed by “Linear Combinations” of the EM integral operators.In contrast,the proposed method is the first attempt to construct IE-ODDM based on the integral equation formed by “Non-Linear Combinations” of the EM integral operators.When dealing with situations with dense meshes such as EM multiscale problems,the subdomain iterative solution process will encounter potential slow convergence if previous CFIE-ODDM is adopted.In contrast,the proposed method can always maintain stable inner iteration convergence,thus possessing better overall robustness.7.A sparse representation of inverse integral operator using Neumann series and skeletonization factorization(SR-IIO-NS-SF)is proposed.First,based on the spatial grouping of the basis functions,the impedance matrix of the method of moments(Mo M)is split into the near and far field part.Then,based on the quasi-static property and intrinsic sparsity of the near field matrix,a hierarchical skeletonization factorization without far field proxy surface is constructed,and the sparse factorization of the inverse of the near field matrix is obtained.Finally,using Neumann series,together with the sparse representations of both the far field matrix and the inverse of the near field matrix,the whole inverse integral operator is represented in a discretized form by the combinations of a sequence of “Sums” and “Products” of sparse matrices.The proposed sparse representation is independent of the incident terms,thus possessing some features of fast direct solvers.Numerical experiments demonstrate that,compared with typical Krylov subspace methods such as conjugate gradient method(CG),the solution process of the proposed method is more efficient.Besides,for multiscale cases,the proposed method is more robust.Furthermore,the proposed method provides a novel entry point for further research on high frequency fast direct solvers in the EM community.