A fast multipole boundary element method for 2D multi-domain elastostatic problems based on a dual BIE formulation

A new fast multipole formulation for the hypersingular BIE (HBIE) for 2D elasticity is presented in this paper based on a complex-variable representation of the kernels, similar to the formulation developed earlier for the conventional BIE (CBIE). A dual BIE formulation using a linear combination of the developed CBIE and HBIE is applied to analyze multi-domain problems with thin inclusions or open cracks. Two pre-conditioners for the fast multipole boundary element method (BEM) are devised and their effectiveness and efficiencies in solving large-scale problems are discussed. Several numerical examples are presented to study the accuracy and efficiency of the developed fast multipole BEM using the dual BIE formulation. The numerical results clearly demonstrate the potentials of the fast multipole BEM for solving large-scale 2D multi-domain elasticity problems. The method can be applied to study composite materials, functionally-graded materials, and micro-electro-mechanical-systems with coupled fields, all of which often involve thin shapes or thin inclusions.     

A fast multipole boundary element method for solving two-dimensional thermoelasticity problems

A fast multipole boundary element method (BEM) for solving general uncoupled steady-state thermoelasticity problems in two dimensions is presented in this paper. The fast multipole BEM is developed to handle the thermal term in the thermoelasticity boundary integral equation involving temperature and heat flux distributions on the boundary of the problem domain. Fast multipole expansions, local expansions and related translations for the thermal term are derived using complex variables. Several numerical examples are presented to show the accuracy and effectiveness of the developed fast multipole BEM in calculating the displacement and stress fields for 2-D elastic bodies under various thermal loads, including thin structure domains that are difficult to mesh using the finite element method (FEM). The BEM results using constant elements are found to be accurate compared with the analytical solutions, and the accuracy of the BEM results is found to be comparable to that of the FEM with linear elements. In addition, the BEM offers the ease of use in generating the mesh for a thin structure domain or a domain with complicated geometry, such as a perforated plate with randomly distributed holes for which the FEM fails to provide an adequate mesh. These results clearly demonstrate the potential of the developed fast multipole BEM for solving 2-D thermoelasticity problems.     

A dual BIE approach for large‐scale modelling of 3‐D electrostatic problems with the fast multipole boundary element method

A dual boundary integral equation (BIE) formulation is presented for the analysis of general 3‐D electrostatic problems, especially those involving thin structures. This dual BIE formulation uses a linear combination of the conventional BIE and hypersingular BIE on the entire boundary of a problem domain. Similar to crack problems in elasticity, the conventional BIE degenerates when the field outside a thin body is investigated, such as the electrostatic field around a thin conducting plate. The dual BIE formulation, however, does not degenerate in such cases. Most importantly, the dual BIE is found to have better conditioning for the equations using the boundary element method (BEM) compared with the conventional BIE, even for domains with regular shapes. Thus the dual BIE is well suited for implementation with the fast multipole BEM. The fast multipole BEM for the dual BIE formulation is developed based on an adaptive fast multiple approach for the conventional BIE. Several examples are studied with the fast multipole BEM code, including finite and infinite domain problems, bulky and thin plate structures, and simplified comb‐drive models having more than 440 thin beams with the total number of equations above 1.45 million and solved on a PC. The numerical results clearly demonstrate that the dual BIE is very effective in solving general 3‐D electrostatic problems, as well as special cases involving thin perfect conducting structures, and that the adaptive fast multipole BEM with the dual BIE formulation is very efficient and promising in solving large‐scale electrostatic problems. Copyright © 2007 John Wiley & Sons, Ltd.     

The fast multipole boundary element method for potential problems: A tutorial

The fast multipole method (FMM) has been regarded as one of the top 10 algorithms in scientific computing that were developed in the 20th century. Combined with the FMM, the boundary element method (BEM) can now solve large-scale problems with several million degrees of freedom on a desktop computer within hours. This opened up a wide range of applications for the BEM that has been hindered for many years by the lack of efficiencies in the solution process, although it has been regarded as superb in the modeling stage. However, understanding the fast multipole BEM is even more difficult as compared with the conventional BEM, because of the added complexities and different approaches in both FMM formulations and implementations. This paper is an introduction to the fast multipole BEM for potential problems, which is aimed to overcome this hurdle for people who are familiar with the conventional BEM and want to learn and adopt the fast multipole approach. The basic concept and main procedures in the FMM for solving boundary integral equations are described in detail using the 2D potential problem as an example. The structure of a fast multipole BEM program is presented and the source code is also made available that can help the development of fast multipole BEM codes for solving other problems. Numerical examples are presented to further demonstrate the efficiency, accuracy and potentials of the fast multipole BEM for solving large-scale problems.     

Analytical integration of the moments in the diagonal form fast multipole boundary element method for 3-D acoustic wave problems

A diagonal form fast multipole boundary element method (BEM) is presented in this paper for solving 3-D acoustic wave problems based on the Burton-Miller boundary integral equation (BIE) formulation. Analytical expressions of the moments in the diagonal fast multipole BEM are derived for constant elements, which are shown to be more accurate, stable and efficient than those using direct numerical integration. Numerical examples show that using the analytical moments can reduce the CPU time by a lot as compared with that using the direct numerical integration. The percentage of CPU time reduction largely depends on the proportion of the time used for moments calculation to the overall solution time. Several examples are studied to investigate the effectiveness and efficiency of the developed diagonal fast multipole BEM as compared with earlier p³ fast multipole method BEM, including a scattering problem of a dolphin modeled with 404,422 boundary elements and a radiation problem of a train wheel track modeled with 257,972 elements. These realistic, large-scale BEM models clearly demonstrate the effectiveness, efficiency and potential of the developed diagonal form fast multipole BEM for solving large-scale acoustic wave problems.     

Adaptive fast multipole boundary element method for three-dimensional half-space acoustic wave problems

A new adaptive fast multipole boundary element method (BEM) for solving 3-D half-space acoustic wave problems is presented in this paper. The half-space Green's function is employed explicitly in the boundary integral equation (BIE) formulation so that a tree structure of the boundary elements only for the boundaries of the real domain need to be applied, instead of using a tree structure that contains both the real domain and its mirror image. This procedure simplifies the implementation of the adaptive fast multipole BEM and reduces the CPU time and memory storage by about a half for large-scale half-space problems. An improved adaptive fast multipole BEM is presented for the half-space acoustic wave problems, based on the one developed recently for the full-space problems. This new fast multipole BEM is validated using several simple half-space models first, and then applied to model 3-D sound barriers and a large-scale windmill model with five turbines. The largest BEM model with 557470 elements was solved in about an hour on a desktop PC. The accuracy and efficiency of the BEM results clearly show the potential of the adaptive fast multipole BEM for solving large-scale half-space acoustic wave problems that are of practical significance.     

A new fast multipole boundary element method for solving large‐scale two‐dimensional elastostatic problems

A new fast multipole boundary element method (BEM) is presented in this paper for large‐scale analysis of two‐dimensional (2‐D) elastostatic problems based on the direct boundary integral equation (BIE) formulation. In this new formulation, the fundamental solution for 2‐D elasticity is written in a complex form using the two complex potential functions in 2‐D elasticity. In this way, the multipole and local expansions for 2‐D elasticity BIE are directly linked to those for 2‐D potential problems. Furthermore, their translations (moment to moment, moment to local, and local to local) turn out to be exactly the same as those in the 2‐D potential case. This formulation is thus very compact and more efficient than other fast multipole approaches for 2‐D elastostatic problems using Taylor series expansions of the fundamental solution in its original form. Several numerical examples are presented to study the accuracy and efficiency of the developed fast multipole BEM formulation and code. BEM models with more than one million equations have been solved successfully on a laptop computer. These results clearly demonstrate the potential of the developed fast multipole BEM for solving large‐scale 2‐D elastostatic problems. Copyright © 2005 John Wiley & Sons, Ltd.     

An <i>O(N)</i> Fast Multipole Hybrid Boundary Node Method for 3D Elasticity

The Hybrid boundary node method (Hybrid BNM) is a boundary type meshless method which based on the modified variational principle and the Moving Least Squares (MLS) approximation. Like the boundary element method (BEM), it has a dense and unsymmetrical system matrix and needs to be speeded up while solving large scale problems. This paper combines the fast multipole method (FMM) with Hybrid BNM for solving 3D elasticity problems. The formulations of the fast multipole Hybrid boundary node method (FM-HBNM) which based on spherical harmonic series are given. The computational cost is estimated and an O(N) algorithm is obtained. The algorithm is implemented on a computer code written in C++. Numerical results demonstrate the accuracy and efficiency of the proposed technique.     

An adaptive fast multipole boundary element method for three-dimensional acoustic wave problems based on the Burton–Miller formulation

The high solution costs and non-uniqueness difficulties in the boundary element method (BEM) based on the conventional boundary integral equation (CBIE) formulation are two main weaknesses in the BEM for solving exterior acoustic wave problems. To tackle these two weaknesses, an adaptive fast multipole boundary element method (FMBEM) based on the Burton–Miller formulation for 3-D acoustics is presented in this paper. In this adaptive FMBEM, the Burton–Miller formulation using a linear combination of the CBIE and hypersingular BIE (HBIE) is applied to overcome the non-uniqueness difficulties. The iterative solver generalized minimal residual (GMRES) and fast multipole method (FMM) are adopted to improve the overall computational efficiency. This adaptive FMBEM for acoustics is an extension of the adaptive FMBEM for 3-D potential problems developed by the authors recently. Several examples on large-scale acoustic radiation and scattering problems are presented in this paper which show that the developed adaptive FMBEM can be several times faster than the non-adaptive FMBEM while maintaining the accuracies of the BEM.     

Dynamic analysis of shear deformable plates using the Dual Reciprocity Method

The Dual Reciprocity Method is a popular mathematical technique to treat domain integrals in the boundary element method (BEM). This technique has been used to treat inertial integrals in the dynamic thin plate bending analysis using a direct formulation of the BEM based on the elastostatic fundamental solution of the problem. In this work, this approach was applied for the dynamic analysis of shear deformable plates based on the Reissner plate bending theory, considering the rotary inertia of the plate. Three kinds of problems: modal, harmonic and transient dynamic analysis, were analyzed. Numerical examples are presented to demonstrate the efficiency and accuracy of the proposed formulation.     

Error analysis and novel near-field preconditioning techniques for Taylor series multipole-BEM

The Taylor series multipole boundary element method (TSMBEM) improves the efficiency of boundary element method (BEM) by reducing the required operations and computer memory. However, the precision of TSMBEM is sacrificed comparing to the conventional BEMs. To quantify the accuracy of TSMBEM in solving 3D elasticity problems, error analysis is performed. A novel near-field preconditioning technique is presented for fast multipole-BEM based on the degressive regularity of fundamental solutions. The correctness and effectiveness of error estimate formula and near-field preconditioning technique is demonstrated by numerical examples.     

Fast Fourier transform on multipoles (FFTM) algorithm for Laplace equation with direct and indirect boundary element method

In this paper, the fast Fourier transform on multipole (FFTM) algorithm is used to accelerate the matrix-vector product in the boundary element method (BEM) for solving Laplace equation. This is implemented in both the direct and indirect formulations of the BEM. A new formulation for handling the double layer kernel using the direct formulation is presented, and this is shown to be related to the method given by Yoshida (Application of fast multipole method to boundary integral equation method, Kyoto University, Japan, 2001). The FFTM algorithm shows different computational performances in direct and indirect formulations. The direct formulation tends to take more computational time due to the evaluation of an extra integral. The error of FFTM in the direct formulation is smaller than that in the indirect formulation because the direct formulation has the advantage of avoiding the calculations of the free term and the strongly singular integral explicitly. The multipole and local translations introduce approximation errors, but these are not significant compared with the discretization error in the direct or indirect BEM formulation. Several numerical examples are presented to compare the computational efficiency of the FFTM algorithm used with the direct and indirect BEM formulations.     

A wideband fast multipole boundary element method for three dimensional acoustic shape sensitivity analysis based on direct differentiation method

This paper presents a wideband fast multipole boundary element approach for three dimensional acoustic shape sensitivity analysis. The Burton-Miller method is adopted to tackle the fictitious eigenfrequency problem associated with the conventional boundary integral equation method in solving exterior acoustic wave problems. The sensitivity boundary integral equations are obtained by the direct differentiation method, and the concept of material derivative is used in the derivation. The iterative solver generalized minimal residual method (GMRES) and the wideband fast multipole method are employed to improve the overall computational efficiency. Several numerical examples are given to demonstrate the accuracy and efficiency of the present method.     

激光干涉仪反射镜三维温度场的快速多极边界元分析

温差造成光刻机激光干涉仪反射镜热变形,从而影响光刻机的精度。该文将基于二次单元的快速边界元法用于激光干涉仪反射镜的大规模温度场模拟。不连续单元的引入可以有效处理角点问题;新型快速多极算法用于边界元法的加速求解。建立统一的二次单元多极展开格式以处理混合边界。数值算例分析了快速多极边界元法的计算精度和效率,并和常规算法比较;使用该算法对激光干涉仪反射镜进行了大规模温度场计算,并和有限元法比较。结果表明:基于二次单元的快速多极边界元法可以高精度求解大规模三维传热问题。     

Identities for the fundamental solution of thin plate bending problems and the nonuniqueness of the hypersingular BIE solution for multi-connected domains

Four integral identities for the fundamental solution of thin plate bending problems are presented in this paper. These identities can be derived by imposing rigid-body translation and rotation solutions to the two direct boundary integral equations (BIEs) for plate bending problems, or by integrating directly the governing equation for the fundamental solution. These integral identities can be used to develop weakly-singular and nonsingular forms of the BIEs for plate bending problems. They can also be employed to show the nonuniqueness of the solution of the hypersingular BIE for plates on multi-connected (or multiply-connected) domains. This nonuniqueness is shown for the first time in this paper. It is shown that the solution of the singular (deflection) BIE is unique, while the hypersingular (rotation) BIE can admit an arbitrary rigid-body translation term in the deflection solution, on the edge of a hole. However, since both the singular and hypersingular BIEs are required in solving a plate bending problem using the boundary element method (BEM), the BEM solution is always unique on edges of holes in plates on multi-connected domains. Numerical examples of plates with holes are presented to show the correctness and effectiveness of the BEM for multi-connected domain problems.     

A fast multipole boundary element method for 3D multi-domain acoustic scattering problems based on the Burton-Miller formulation

A fast multipole boundary element method (FMBEM) for 3D multi-domain acoustic scattering problems based on the Burton-Miller formulation is presented in this paper. A multi-tree structure is designed for the multi-domain FMBEM. It results in mismatch of leaves and well separate cells definition in different domains and complicates the implementation of the algorithm, especially for preconditioning. A preconditioner based on boundary blocks is devised for the multi-domain FMBEM and its efficiency in reducing the number of iterations in solving large-scale multi-domain scattering problems is demonstrated. In addition to the analytical moment, another method, based on the anti-symmetry of the moment kernel, is developed to reduce the moment computation further by a factor of two. Frequency sweep analysis of a penetrable sphere shows that the multi-domain FMBEM based on the Burton-Miller formulation can overcome the non-unique solution problem at the fictitious eigenfrequencies. Several other numerical examples are presented to demonstrate the accuracy and efficiency of the developed multi-domain FMBEM for acoustic problems. In spite of the high cost of memory and CPU time for the multi-tree structure in the multi-domain FMBEM, a large BEM model studied with a PC has 0.3 million elements corresponding to 0.6 million unknowns, which clearly shows the potential of the developed FMBEM in solving large-scale multi-domain acoustics problems.     

A fast multipole boundary element method based on the improved Burton–Miller formulation for three-dimensional acoustic problems

A fast multipole boundary element method (FMBEM) based on the improved Burton–Miller formulation is presented in this paper for solving large-scale three-dimensional (3D) acoustic problems. Some improvements can be made for the developed FMBEM. In order to overcome the non-unique problems of the conventional BEM, the FMBEM employs the improved Burton–Miller formulation developed by the authors recently to solve the exterior acoustic problems for all wave numbers. The improved Burton–Miller formulation contains only weakly singular integrals, and avoids the numerical difficulties associated to the evaluation of the hypersingular integral, it leads to the numerical implementations more efficient and straightforward. In this study, the fast multipole method (FMM) and the preconditioned generalized minimum residual method (GMRES) iterative solver are applied to solve system matrix equation. The block diagonal preconditioner needs no extra memory and no extra CPU time in each matrix–vector product. Thus, the overall computational efficiency of the developed FMBEM is further improved. Numerical examples clearly demonstrate the accuracy, efficiency and applicability of the FMBEM based on improved Burton–Miller formulation for large-scale acoustic problems.     

A fast algorithm for three-dimensional electrostatics analysis: fast Fourier transform on multipoles (FFTM)

In this paper, we propose a new fast algorithm for solving large problems using the boundary element method (BEM). Like the fast multipole method (FMM), the speed-up in the solution of the BEM arises from the rapid evaluations of the dense matrix–vector products required in iterative solution methods. This fast algorithm, which we refer to as fast Fourier transform on multipoles (FFTM), uses the fast Fourier transform (FFT) to rapidly evaluate the discrete convolutions in potential calculations via multipole expansions. It is demonstrated that FFTM is an accurate method, and is generally more accurate than FMM for a given order of multipole expansion (up to the second order). It is also shown that the algorithm has approximately linear growth in the computational complexity, implying that FFTM is as efficient as FMM. Copyright © 2004 John Wiley & Sons, Ltd.     

An adaptive fast multipole boundary face method with higher order elements for acoustic problems in three-dimension

An adaptive fast multipole boundary face method using higher order elements based on the well-known Burton-Miller equation is presented in this paper for solving the large-scale three-dimensional exterior acoustic wave problems. The fast multipole boundary face method is referred to as FMBFM. In the FMBFM, the boundary integration and field variables approximation are both performed in the parametric space of each boundary face exactly the same as the B-rep data structure in standard solid modeling packages. In this FMBFM, higher order elements are employed to improve the computational accuracy and efficiency, and an adaptive tree structure is constructed to improve the efficiency of the FMBFM. Numerical examples for large-scale acoustic radiation and scattering problems in this paper demonstrated the accuracy, efficiency and validity of the adaptive FMBFM. Comparison study showed that the FMBFM with high order elements out-performs the FMBFM with constant elements respect to accuracy and CPU time at the same number of the nodes. In addition, the CAD models, even with complicated geometry, are directly converted into the FMBFM models, thus the present method provides a new way toward automatic simulation.