APPLICATION OF A NEW FAST MULTIPOLE BEM FOR SIMULATION OF 2D ELASTIC SOLID WITH LARGE NUMBER OF INCLUSIONS

A fast multipole method(FMM)is applied for BEM to reduce both the operation and memory requirement in dealing with very large scale problems.In this paper,a new version of fast multipole BEM for 2D elastostatics is presented and used for simulation of 2D elastic solid with a large number of randomly distributed inclusions combined with a similar subregion approach.Generalized minimum residual method(GMRES)is used as an iterative solver to solve the equation system formed by BEM iteratively.The numerical results show that the scheme presented is applicable to certain large scale problems.

Improvement and performance of parallel multilevel fast multipole algorithm

The method of establishing data structures plays an important role in the efficiency of parallel multilevel fast multipole algorithm（PMLFMA）.Considering the main complements of multilevel fast multipole algorithm（MLFMA） memory,a new parallelization strategy and a modified data octree construction scheme are proposed to further reduce communication in order to improve parallel efficiency.For far interaction,a new scheme called dynamic memory allocation is developed.To analyze the workload balancing performance of a parallel implementation,the original concept of workload balancing factor is introduced and verified by numerical examples.Numerical results show that the above measures improve the parallel efficiency and are suitable for the analysis of electrical large-scale scattering objects.

A parallel fast multipole BEM and its applications to large-scale analysis of 3-D fiber-reinforced composites

In this paper, an adaptive boundary element method （BEM） is presented for solving 3-D elasticity problems. The numerical scheme is accelerated by the new version of fast multipole method （FMM） and parallelized on distributed memory architectures. The resulting solver is applied to the study of representative volume element （RVE） for short fiberreinforced composites with complex inclusion geometry. Numerical examples performed on a 32-processor cluster show that the proposed method is both accurate and efficient, and can solve problems of large size that are challenging to existing state-of-the-art domain methods.

Application of A Fast Multipole BIEM for Flow Diffraction from A 3D Body

A Fast Multipole Method (FMM) is developed as a numerical approach to the reduction of the computational cost and requirement memory capacity for a large in solving large-scale problems. In this paper it is applied to the boundary integral equation method (BIEM) for current diffraction from arbitrary 3D bodies. The boundary integral equation is discretized by higher order elements, the FMM is applied to avoid the matrix/vector product, and the resulting algebraic equation is solved by the Generalized Conjugate Residual method (GCR). Numerical examination shows that the FMM is more efficient than the direct evaluation method in computational cost and storage of computers.

Efficient analysis of dielectric radomes using multilevel fast multipole algorithm with CRWG basis

A full-wave analysis of the electromagnetic problem of a three-dimensional （3-D） antenna radiating through a 3-D dielectric radome is preserued. The problem is formulated using the Poggio-Miller-Chang-Harrington- Wu（PMCHW） approach for homogeneous dielectric objects and the electric field integral equation for conducting objects. The integral equations are discretized by the method of moment （MoM）, in which the conducting and dielectric surface/interfaces are represented by curvilinear triangular patches and the unknown equivalent electric and magnetic currents are expanded using curvilinear RWG basis functions. The resultant matrix equation is then solved by the multilevel fast multipole algorithm （MLFMA） and fast far-field approximation （FAFFA） is used to further accelerate the computation. The radiation patterns of dipole arrays in the presence of radomes are presented. The numerical results demonstrate the accuracy and versatility of this method.

General and efficient parallel approach of finite element-boundary integral-multilevel fast multipole algorithm

A general and efficient parallel approach is proposed for the first time to parallelize the hybrid finiteelement-boundary-integral-multi-level fast multipole algorithm （FE-BI-MLFMA）. Among many algorithms of FE-BI-MLFMA, the decomposition algorithm （DA） is chosen as a basis for the parallelization of FE-BI-MLFMA because of its distinct numerical characteristics suitable for parallelization. On the basis of the DA, the parallelization of FE-BI-MLFMA is carried out by employing the parallelized multi-frontal method for the matrix from the finiteelement method and the parallelized MLFMA for the matrix from the boundary integral method respectively. The programming and numerical experiments of the proposed parallel approach are carried out in the high perfor- mance computing platform CEMS-Liuhui. Numerical experiments demonstrate that FE-BI-MLFMA is efficiently parallelized and its computational capacity is greatly improved without losing accuracy, efficiency, and generality.

A wideband fast multipole boundary element method for half-space/plane-symmetric acoustic wave problems

This paper presents a novel wideband fast multipole boundary element approach to 3D half-space/planesymmetric acoustic wave problems.The half-space fundamental solution is employed in the boundary integral equations so that the tree structure required in the fast multipole algorithm is constructed for the boundary elements in the real domain only.Moreover,a set of symmetric relations between the multipole expansion coefficients of the real and image domains are derived,and the half-space fundamental solution is modified for the purpose of applying such relations to avoid calculating,translating and saving the multipole/local expansion coefficients of the image domain.The wideband adaptive multilevel fast multipole algorithm associated with the iterative solver GMRES is employed so that the present method is accurate and efficient for both lowand high-frequency acoustic wave problems.As for exterior acoustic problems,the Burton-Miller method is adopted to tackle the fictitious eigenfrequency problem involved in the conventional boundary integral equation method.Details on the implementation of the present method are described,and numerical examples are given to demonstrate its accuracy and efficiency.

Diagonal form fast multipole boundary element method for 2D acoustic problems based on Burton-Miller boundary integral equation formulation and its applications

This paper describes formulation and implementation of the fast multipole boundary element method （FMBEM） for 2D acoustic problems. The kernel function expansion theory is summarized, and four building blocks of the FMBEM are described in details. They are moment calculation, moment to moment translation, moment to local translation, and local to local translation. A data structure for the quad-tree construction is proposed which can facilitate implementation. An analytical moment expression is derived, which is more accurate, stable, and efficient than direct numerical computation. Numerical examples are presented to demonstrate the accuracy and efficiency of the FMBEM, and radiation of a 2D vibration rail mode is simulated using the FMBEM.

Fast multipole boundary element analysis of 2D viscoelastic composites with imperfect interfaces

A fast multipole boundary element method(FMBEM)is developed for the analysis of 2D linear viscoelastic composites with imperfect viscoelastic interfaces.The transformed fast multipole formulations are established using the time domain method. To simulate the viscoelastic behavior of imperfect interfaces that are frequently encountered in practice,the Kelvin type model is introduced.The FMBEM is further improved by incorporating naturally the interaction among inclusions as well as eliminating the phenomenon of material penetration.Since all the integrals are evaluated analytically,high accuracy and fast convergence of the numerical scheme are obtained.Several numerical examples,including planar viscoelastic composites with a single inclusion or randomly distributed multi-inclusions are presented.The numerical results are compared with the developed analytical solutions,which illustrates that the proposed FMBEM is very efficient in determining the macroscopic viscoelastic behavior of the particle-reinforced composites with the presence of imperfect interfaces.The laboratory measurements of the mixture creep compliance of asphalt concrete are also compared with the prediction by the developed model.

Fast Multipole BEM for Simulation of 2-D Solids Containing Large Numbers of Cracks

The fast multipole method was used to solve the traction boundary integral equation for 2-D crack analysis. The use of both multipole and local expansions reduces both the computational complexity and the memory requirement to O(N). The multipole expansion uses a complex Taylor series expansion to reduce the number of multipole moments. The generalized minimum residual method solver (GMRES) was selected as the iterative solver. An improved preconditioner for GMRES was developed which uses less CPU time and less memory. A new initial candidate vector for the iterative solver was developed to further improve the efficiency. The numerical examples apply the method to the analysis of cracks in infinite 2-D space with the largest model having 900 000 degrees of freedom.

Analysis of Numerical Integration Error for Bessel Integral Identity in Fast Multipole Method for 2D Helmholtz Equation

In 2D fast multipole method for scattering problems,square quadrature rule is used to discretize the Bessel integral identity for diagonal expansion of 2D Helmholtz kernel,and numerical integration error is introduced. Taking advantage of the relationship between Euler-Maclaurin formula and trapezoidal quadrature rule,and the relationship between trapezoidal and square quadrature rule,sharp computable bound with analytical form on the error of numerical integration of Bessel integral identity by square quadrature rule is derived in this paper. Numerical experiments are presented at the end to demonstrate the accuracy of the sharp computable bound on the numerical integration error.

A pedestrian introduction to fast multipole methods

This paper provides a conceptual and non-rigorous description of the fast multipole methods for evaluating convolution kernel functions with source distributions.Both the non-oscillatory and the oscillatory kernels are considered.For non-oscillatory kernel,we outline the main ideas of the classical fast multipole method proposed by Greengard and Rokhlin.In the oscillatory case,the directional fast multipole method developed recently by Engquist and Ying is presented.

Fast multipole accelerated boundary element method for the Helmholtz equation in acoustic scattering problems

We apply the fast multipole method (FMM) accelerated boundary element method (BEM) for the three-dimensional (3D) Helmholtz equation, and as a result, large-scale acoustic scattering problems involving 400000 elements are solved efficiently. This is an extension of the fast multipole BEM for two-dimensional (2D) acoustic problems developed by authors recently. Some new improvements are obtained. In this new technique, the improved Burton-Miller formulation is employed to over-come non-uniqueness difficulties in the conventional BEM for exterior acoustic problems. The computational efficiency is further improved by adopting the FMM and the block diagonal preconditioner used in the generalized minimum residual method (GMRES) iterative solver to solve the system matrix equation. Numerical results clearly demonstrate the complete reliability and efficiency of the proposed algorithm. It is potentially useful for solving large-scale engineering acoustic scattering problems.

Acceleration of unsteady vortex lattice method via dipole panel fast multipole method

The Unsteady Vortex Lattice Method(UVLM) is a medium-fidelity aerodynamic tool that has been widely used in aeroelasticity and flight dynamics simulations. The most timeconsuming step is the evaluation of the induced velocity. Supposing that the number of bound and wake lattices is N and the computational cost is O (N2), we present an OeNT Dipole Panel Fast Multipole Method(DPFMM) for the rapid evaluation of the induced velocity in UVLM. The multipole expansion coefficients of a quadrilateral dipole panel have been derived in spherical coordinates, whose accuracy is the same as that of the Biot-Savart kernel at the same truncation degree P.Two methods(the loosening method and the shrinking method) are proposed and tested for space partitioning volumetric panels. Compared with FMM for vortex filaments(with three harmonics),DPFMM is approximately two times faster for N2 [103,106]. The simulation time of a multirotor(N~104) is reduced from 100 min(with unaccelerated direct solver) to 2 min(with DPFMM).

Large Scale Analysis of Mechanical Properties in 3-D Fiber-Reinforced Composites Using a New Fast Multipole Boundary Element Method

Fiber-reinforced composites are commonly used in various engineering applications. The mechanical properties of such composites depend strongly on micro-structural parameters. This paper presents a new boundary element method （BEM） for numerical analysis of the mechanical properties of 3-D fiberreinforced composites. Acceleration of the BEM is achieved by means of a fast multipole method （FMM）, in allowing large scale simulations of a finite elastic domain containing up to 100 elastic fibers to be performed on one personal computer. The maximum number of degrees of freedom can reach a value of over 250 000. The effects of several key micro-structural parameters on the local stress fields and on the effective elastic moduli of fiber-reinforced composites are evaluated. The numerical results are compared with analytical predictions and good agreement is observed. The results show that the fast multipole BEM could be a promising tool for further understanding of the mechanical behavior of such composites.

A Preconditioned 3-DMulti-Region Fast Multipole Solver for Seismic Wave Propagation in Complex Geometries

The analysis of seismic wave propagation and amplification in complex geological structures requires efficient numerical methods.In this article,following up on recent studies devoted to the formulation,implementation and evaluation of 3-D single-and multi-region elastodynamic fast multipole boundary element methods(FM-BEMs),a simple preconditioning strategy is proposed.Its efficiency is demonstrated on both the single-andmulti-region versions using benchmark examples(scattering of plane waves by canyons and basins).Finally,the preconditioned FM-BEM is applied to the scattering of plane seismic waves in an actual configuration(alpine basin of Grenoble,France),for which the high velocity contrast is seen to significantly affect the overall efficiency of the multi-region FM-BEM.

A New Directional Algebraic Fast Multipole Method Based Iterative Solver for the Lippmann-Schwinger Equation Accelerated with HODLR Preconditioner

We present a fast iterative solver for scattering problems in 2D,where a penetrable object with compact support is considered.By representing the scattered field as a volume potential in terms of the Green’s function,we arrive at the Lippmann-Schwinger equation in integral form,which is then discretized using an appropriate quadrature technique.The discretized linear system is then solved using an iterative solver accelerated by Directional Algebraic Fast Multipole Method(DAFMM).The DAFMM presented here relies on the directional admissibility condition of the 2D Helmholtz kernel[1],and the construction of low-rank factorizations of the appropriate low-rank matrix sub-blocks is based on our new Nested Cross Approximation(NCA)[2].The advantage of the NCA described in[2]is that the search space of so-called far-field pivots is smaller than that of the existing NCAs[3,4].Another significant contribution of this work is the use of HODLR based direct solver[5]as a preconditioner to further accelerate the iterative solver.In one of our numerical experiments,the iterative solver does not converge without a preconditioner.We show that the HODLR preconditioner is capable of solving problems that the iterative solver can not.Another noteworthy contribution of this article is that we perform a comparative study of the HODLR based fast direct solver,DAFMMbased fast iterative solver,and HODLR preconditioned DAFMM based fast iterative solver for the discretized Lippmann-Schwinger problem.To the best of our knowledge,this work is one of the first to provide a systematic study and comparison of these different solvers for various problem sizes and contrast functions.In the spirit of reproducible computational science,the implementation of the algorithms developed in this article is made available at https://github.com/vaishna77/Lippmann_Schwinger_Solver.

FAST MULTIPOLE SINGULAR BOUNDARY METHOD FOR LARGE-SCALE PLANE ELASTICITY PROBLEMS

The singular boundary method （SBM） is a recent meshless boundary collocation method that remedies the perplexing drawback of fictitious boundary in the method of fundamental solutions （MFS）. The basic idea is to use the origin intensity factor to eliminate singularity of the fundamental solution at source. The method has so far been applied successfully to the potential and elasticity problems. However, the SBM solution for large-scale problems has been hindered by the operation count of O（N^3） with direct solvers or O（N^2） with iterative solvers, as well as the memory requirement of O（N^2）. In this study, the first attempt was made to combine the fast multipole method （FMM） and the SBM to significantly reduce CPU time and memory requirement by one degree of magnitude, namely, O（N）. Based on the complex variable represen- tation of fundamental solutions, the FMM-SBM formulations for both displacement and traction were presented. Numerical examples with up to hundreds of thousands of unknowns have successfully been tested on a desktop computer. These results clearly illustrated that the proposed FMM-SBM was very efficient and promising in solving large-scale plane elasticity problems.

Mathematical and Numerical Aspects of the Adaptive Fast Multipole Poisson-Boltzmann Solver

This paper summarizes the mathematical and numerical theories and computational elements of the adaptive fast multipole Poisson-Boltzmann(AFMPB)solver.We introduce and discuss the following components in order:the Poisson-Boltzmann model,boundary integral equation reformulation,surface mesh generation,the nodepatch discretization approach,Krylov iterative methods,the new version of fast multipole methods(FMMs),and a dynamic prioritization technique for scheduling parallel operations.For each component,we also remark on feasible approaches for further improvements in efficiency,accuracy and applicability of the AFMPB solver to largescale long-time molecular dynamics simulations.The potential of the solver is demonstrated with preliminary numerical results.

Fast Multipole Accelerated Boundary Integral Equation Method for Evaluating the Stress Field Associated with Dislocations in a Finite Medium

In this paper,we develop an efficient numericalmethod based on the boundary integral equation formulation and new version of fast multipole method to solve the boundary value problem for the stress field associated with dislocations in a finite medium.Numerical examples are presented to examine the influence from material boundaries on dislocations.