Multilevel fast multipole algorithm for electromagnetic scatteringby large complex objects

The fast multipole method (FMM) and multilevel fast multipole algorithm (MLFMA) are reviewed. The number of modes required, block-diagonal preconditioner, near singularity extraction, and the choice of initial guesses are discussed to apply the MLFMA to calculating electromagnetic scattering by large complex objects. Using these techniques, we can solve the problem of electromagnetic scattering by large complex three-dimensional (3-D) objects such as an aircraft (VFY218) on a small computer     

A fast multipole-method-based calculation of the capacitance matrixfor multiple conductors above stratified dielectric media

An efficient static fast-multipole-method (FMM)-based algorithm is presented in this paper for the evaluation of the parasitic capacitance of three-dimensional microstrip signal lines above stratified dielectric media. The effect of dielectric interfaces on the capacitance matrix is included in the stage of FMM when outgoing multipole expansions are used to form local multipole expansions by the use of interpolated image outgoing-to-local multipole translation functions. The increase in computation time and memory usage, compared to the free-space case, is, therefore, small. The algorithm retains O(N) computational and memory complexity of the free-space FMM, where N is the number of conductor patches     

An efficient perfectly matched layer based multilevel fast multipole algorithm for large planar microwave structures

An efficient multilevel fast multipole algorithm (MLFMA) formalism to model radiation and scattering by/from large planar microwave structures is presented. The technique relies on an electric field integral equation (EFIE) formulation and a series expansion for the Green dyadic, based on the use of perfectly matched layers (PML). In this way, a new PML-MLFMA is developed to efficiently evaluate matrix-vector multiplications arising in the iterative solution of the scattering problem. The computational complexity of the new algorithm scales down to O(N) for electrically large structures. The theory is validated by means of several illustrative, numerical examples.     

Fast multipole method for scattering from an arbitrary PEC targetabove or buried in a lossy half space

The fast multipole method (FMM) was originally developed for perfect electric conductors (PECs) in free space, through exploitation of the spectral properties of the free-space Green's function. In the work reported here, the FMM is modified, for scattering from an arbitrary three-dimensional (3-D) PEC target above or buried in a lossy half space. The “near” terms in the FMM are handled via the original method-of-moments (MoM) analysis, wherein the half-space Green's function is evaluated efficiently and rigorously through application of the method of complex images. The “far” FMM interactions, which employ a clustering of expansion and testing functions, utilize an approximation to the Green's function dyadic via real image sources and far-field reflection dyadics. The half-space FMM algorithm is validated through comparison with results computed via a rigorous MoM analysis. Further, a detailed comparison is performed on the memory and computational requirements of the MoM and FMM algorithms for a target in the vicinity of a half-space interface     

Acceleration of Fast Multipole Method for Large-Scale Periodic Structures With Finite Sizes Using Sub-Entire-Domain Basis Functions

An acceleration technique to the fast multipole method (FMM) has been proposed to handle large-scale problems of periodic structures in free space with finite sizes based on the accurate sub-entire-domain basis functions. In the proposed algorithm, only nine (or 27) elements in the whole impedance matrix are required to be computed and stored for a two-dimensional (or three-dimensional) periodic structure, and the matrix-vector multiply can be performed efficiently using the combination of fast Fourier transform and FMM. The theoretical analysis and numerical results show that both the memory requirement and computational complexity are only of the order of O(N) with small constants, where N is the total number of unknowns     

Comparison of three FMM techniques for solving hybrid FE-BI systems

By virtue of its low operation count, the application of the fast multipole method (FMM) results in a substantial speed-up of the boundary-integral (BI) portion of the hybrid finite-element/boundary-integral technique, independent of the shape of the BI contour. Previously, various versions of the fast multipole method have been proposed, each introducing a different approximation to the implementation of the boundary integral. The main goal of this paper is to provide a comparison of the various FMM approaches on the basis of implementation, CPU time, and accuracy. To gain an appreciation of the differences among the various FMM methodologies, a large portion of the paper is devoted to a discussion of the algorithms at a tutorial level. Flow charts and pseudo-code are also given, at sufficient detail to facilitate their implementation. We present quantitative CPU and memory requirements, using the scattering by a groove as the basis for comparison, and conclude that the FMM can accelerate the BI computation without any significant deterioration in accuracy. A simpler FMM-based algorithm results in a much smaller execution time but has a larger error. However, it turns out that a third algorithm, designated the “windowed” FMM, provides a very good compromise with respect to error and execution time. The paper concludes with the presentation of some three-dimensional applications for which a hybrid FE-BI technique, in conjunction with a fast-integral algorithm, is well suited     

快速多极子和遗传算法在电磁成像中的应用

从电磁场的积分方程出发,利用快速多极子（ＦＭＭ）加速矩量法（ＭｏＭ）计算导体柱电磁散射的过程;以散射场的测量值与计算值的平均偏差为目标函数,以导体柱截面形状参数为优化变量,利用遗传算法（ＧＡ）进行优化迭代,来重构目标导体柱的电磁影像。对美国空军ＲＯＭＥ实验室提供的实际数据（Ｉｐｓｗｉｃｈ数据）进行了电磁成像;并给出了对较大导体柱电磁成像的例子。     

Monte Carlo simulation of electromagnetic scattering fromtwo-dimensional random rough surfaces

The fast multipole method fast Fourier transform (FMM-FFT) method is developed to compute the scattering of an electromagnetic wave from a two-dimensional (2-D) rough surface. The resulting algorithm computes a matrix-vector multiply in O(N log N) operations. This algorithm is shown to be more efficient than another O(N log N) algorithm, the multilevel fast multipole algorithm (MLFMA), for surfaces of small height. For surfaces with larger roughness, the MLFMA is found to be more efficient. Using the MLFMA, Monte Carlo simulations are carried out to compute the statistical properties of the electromagnetic scattering from 2-D random rough surfaces using a workstation. For the rougher surface, backscattering enhancement is clearly observable as a pronounced peak in the backscattering direction of the computed bistatic scattering coefficient. For the smoother surface, the Monte Carlo results compare well with the results of the approximate Kirchhoff theory     

有耗半空间环境中导体目标电磁散射的快速分析

应用快速多极子方法求解有耗半空间环境中任意三维金属体的雷达散射特性.对于基函数与测试函数的近场组作用,我们用离散复镜像法严格处理半空间并矢格林函数.在处理远场区时,我们利用实镜像源和反射系数近似计算交界面处远场的作用.通过位于有耗半空间三面角反射器、立方体证明了方法的正确性和有效性.另外,将多分辨预处理器和快速多极子方法结合使得矩阵求解器的迭代次数和计算时间减少数倍.     

用于复杂目标三维矢量散射分析的快速多极子方法

本文着重介绍了一种用于复杂目标三维电磁散射精确建模和数值分析的高型高效数值方法,即快速多极子方法和多层快速多极子方法。     

Parallel implementation of the steepest descent fast multipolemethod (SDFMM) on a Beowulf cluster for subsurface sensing applications

We present the parallel, MPI-based implementation of the SDFMM computer code using a thirty-two node Intel Pentium-based Beowulf cluster. The SDFMM is a fast algorithm that is a hybridization of the method of moments (MoMs), the fast multipole method (FMM), and the steepest descent integration path (SDP), which is used to solve large-scale linear systems of equations produced in electromagnetic scattering problems. An overall speedup of 7.2 has been achieved on the 32-processor Beowulf cluster and a significant reduced runtime is achieved on the 4-processor 667 MHz Alpha workstation     

Efficient MLFMA, RPFMA, and FAFFA algorithms for EM scattering by very large structures

Based on the addition theorem, the principle of a multilevel ray-propagation fast multipole algorithm (RPFMA) and fast far-field approximation (FAFFA) has been demonstrated for three-dimensional (3-D) electromagnetic scattering problems. From a rigorous mathematical derivation, the relation among RPFMA, FAFFA, and a conventional multilevel fast multipole algorithm (MLFMA) has been clearly stated. For very large-scale problems, the translation between groups in the conventional MLFMA is expensive because the translator is defined on an Ewald sphere with many sampling k/spl circ/ directions. When two groups are well separated, the translation can be simplified using RPFMA, where only a few sampling k/spl circ/ directions are required within a cone zone on the Ewald sphere. When two groups are in the far-field region, the translation can be further simplified by using FAFFA where only a single k/spl circ/ is involved in the translator along the ray-propagation direction. Combining RPFMA and FAFFA with MLFMA, three algorithms RPFMA-MLFMA, FAFFA-MLFMA, and RPFMA-FAFFA-MLFMA have been developed, which are more efficient than the conventional MLFMA in 3-D electromagnetic scattering and radiation for very large structures. Numerical results are given to verify the efficiency of the algorithms.     

三维大纵横比目标散射的快速精确求解

采用积分方程法严格求解三维大纵横比目标的电磁散射。在积分方程法的迭代求解中用快速我极子法（ＦＭＭ）加速矩阵与矢量的相乘计算,同时运用快速傅里叶变换（ＦＦＴ）进一步提高快速多极子方法中的转换预计算,数值结果表明：这种快速多极子法－快速傅立叶变换方法（ＦＭＭ－ＦＦＴ）特别适合于三维大纵横比目标的散射求解。     

Fast Solution of Scattering From Conducting Structures by Local MLFMA Based on Improved Electric Field Integral Equation

In this paper, a local multilevel fast multipole algorithm (LMLFMA) based on an improved electric field integral equation (IEFIE) is developed to achieve fast and efficient solution of electromagnetic scattering from 3-D conducting structures. The IEFIE is used to reduce iteration number, and LMLFMA is applied to further accelerate the computation of matrix-vector multiplications in iteration, in which only the local interactions between subscatterers are taken into account. Numerical results show that the present method attains faster iterative convergence than traditional EFIE and less computational cost than MLFMA. The speedup can achieve at least 4–5 times while keeping an rms error of less than 2 dB.      

FMM算法用于二维复杂散射体的RCS计算

利用快速多极子算法(FMM)计算任意形状二维电大尺寸导体加介质体目标的电磁散射，介质体为镶嵌在电大尺寸金属体上的有耗介质。建立金属一介质体的混合积分方程，用共轭梯度法和场量叠代的方法计算散射场，在叠代过程中用快速多极子方法，大大降低计算时间和减小内存要求。数据结果表明该方法的准确和高效。     

快速多极子在任意截面均匀介质柱散射中的应用

采用快速多极子法（FMM）加速后的矩量法（MoM）求解由电磁场等效原理导出的关于均匀介质柱表面等铲电磁流的积分方程,进而计算其电磁散射特性,FMM的引入使计算时间和内存开销都从O(N^2）降到O（N^3/2）,且并不增加多少复杂度。最后给出了一些介质柱体RCS的算例。     

A diagonalized multilevel fast multipole method with spherical harmonics expansion of the k-space Integrals

Diagonalization of the fast multipole method (FMM) for the Helmholtz equation is usually achieved by expanding the multipole representation in propagating plane waves. The resulting k-space integral over the Ewald sphere is numerically evaluated. Storing the k-space quadrature samples of the method of moments (MoM) basis functions constitutes a large portion of the overall memory requirements of the resulting algorithm for solving the integral equations of scattering and radiation problems. In this paper, it is proposed to expand the k-space representation of the basis functions by spherical harmonics in order to reduce the sampling redundancy introduced by numerical quadrature rules. Aggregations, plane wave translations, and disaggregations in the realized multilevel fast multipole method (MLFMM) are carried out using the k-space samples of a numerical quadrature rule. However, the incoming plane waves on the finest MLFMM level are expanded in spherical harmonics again. Thus, due to the orthonormality of spherical harmonics, the testing integrals for the individual testing functions are simplified into series over products of spherical harmonics expansion coefficients. Overall, the resulting MLFMM can save a considerable amount of memory without compromising accuracy and numerical speed.     

快速多极子-边棱元混合算法分析三维非均匀各向异性复杂目标的电磁散射

本文发展了一种能有效分析非均匀各向异性复杂目标的电磁散射特性的三维快速算法;该算法在切向矢量有限元、即边棱元的基础上,采用近年来发展起来的快速多极子算法加速问题的求解,大大降低了计算复杂度,并减小了计算内存.计算实例表明了该方法的有效性和可靠性.     

FMM用于快速计算电大腔体的RCS

利用迭代物理光学法(IPO)计算一般电大尺寸腔体的电磁散射特性,在迭代过程中用快速多极子方法(FMM)加速计算.在雅可比最小残差法(JMRES)的积分运算中引入FMM并与共扼梯度法(CG)的计算效率进行了比较.采用结构化分组,利用转移因子的平移不变性对计算和存储进行了优化.计算结果表明这些加速方法是有效的并能极大地提高计算效率.     

IPO结合FMM，RPFMM，FaFFA方法快速计算电大腔体的RCS

迭代物理光学法结合快速多极子(IPO+FMM)方法,可以快速计算电大腔体的电磁散射特性。传统的快速多极子(FMM)方法需要计算两组的转移因子以及转移过程的全部角谱分量,计算开销是非常大的。随着组间距离的增大,转移过程可以用射线多极子(RPFMM)简化计算,为了充分利用射线多极子方法中参与计算的有效角谱分量随着组间距离增大而变少的特性,采用一种随着组间距离增大自适应调整参与计算的角谱分量的锥形区域的射线多极子方法(RPFMM),当两组距离足够大而位于远场时,用远场近似方法(FaFFA)进一步简化计算。结果表明该方法能在保持计算精度的同时并能较IPO+FMM方法进一步减少计算资源占用、提高计算速度。