Fast multipole method as an efficient solver for 2D elastic wave surface integral equations

The fast multipole method (FMM) is very efficient in solving integral equations. This paper applies the method to solve large solid-solid boundary integral equations for elastic waves in two dimensions. The scattering problem is first formulated with the boundary element method. FMM is then introduced to expedite the solution process. By using the FMM technique, the number of floating-point operations of the matrix-vector multiplication in a standard conjugate gradient algorithm is reduced from O(N ²) to O(N ^1.5), where N is the number of unknowns. The matrix-filling time and the memory requirement are also of the order N ^1.5. The computational complexity of the algorithm is further reduced to O(N ^4/3) by using a ray propagation technique. Numerical results are given to show the accuracy and efficiency of FMM compared to the boundary element method with dense matrix.     

The vectorization expressions of Taylor series multipole-BEM for 3D elasticity problems

The Taylor Series Multipole Boundary Element Method (TSMBEM) can improve the computational efficiency of Boundary Element Methods (BEM) efficiently, which only requires O(N) computational costs (operations and memory) for a problem with N unknowns. But the Taylor expansions of fundamental solutions are generally expressed using tensor form in the literatures about TSMBEM. Although these kinds of formulations are easy to program, many repetitious operations are executed and many equivalent terms are saved, it will result in the waste of memory. It is presented that the vectorization expressions of Taylor series multipole boundary element formula for elasticity problems, which take account of the symmetric properties of fundamental solutions and the characteristic of 3D components. The vectorization formulations reduce the computational operations and storage required, and improve the computational efficiency. The validity and efficiency of proposed scheme are demonstrated by the numerical experiments.     

Fast multipole method applied to Symmetric Galerkin boundary element method for 3D elasticity and fracture problems

The solution of three-dimensional elastostatic problems using the Symmetric Galerkin Boundary Element Method (SGBEM) gives rise to fully populated (albeit symmetric) matrix equations, entailing high solution times for large models. This paper is concerned with the formulation and implementation of a multi-level fast multipole SGBEM (FM-SGBEM) for elastic solid with cracks. Arbitrary geometries and boundary conditions may be considered. Numerical results on test problems involving a cube, single or multiple cracks in an unbounded medium, and a cracked cylindrical solid are presented. BEM models involving up to 10⁶ BEM unknowns are considered, and the desirable predicted trends of the elastostatic FM-SGBEM, such as a O(N) complexity per iteration, are verified.     

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.     

A multipole expansion-based boundary element method for axisymmetric potential problem

The multipole expansion is an approximation technique used to evaluate the potential field due to sources located in the far field. Based on the multipole expansion, we describe a new technique to calculate the far potential field due to ring sources which are encountered in the boundary element method (BEM) formulation of axisymmetric problems. As the sources in the near field are processed by the slower conventional BEM, it is important to maximize the amount of multipole calculations taking advantage of both interior and exterior multipole expansions. Numerical results are presented for an axisymmetric potential test problem with Neumann and Dirichlet boundary conditions. The complexity of the proposed method remains O(N²), which is equal to that of the conventional BEM. However, the proposed technique coupled with an iterative solver speeds up the solution procedure. The technique is significantly advantageous when medium and large numbers of elements are present in the domain.     

Application of the adaptive cross approximation technique for the coupled BE-FE solution of symmetric electromagnetic problems

Electromagnetic devices can be analysed by the coupled BE-FE method, where the conducting and magnetic parts are discretized by finite elements. In contrast, the surrounding space is described with the help of the boundary element method (BEM). This discretization scheme is well suited especially for problems including moving parts (see [12]). The BEM discretization of the boundary integral operators usually leads to dense matrices without any structure. A naive strategy for the solution of the corresponding linear system would need at least O(N ²) operations and memory, where N ist the number of unknowns. Methods such as fast multipole [6] and panel clustering [9] provide an approximation to the matrix in almost linear complexity. These methods are based on explicitly given kernel approximations by degenerate kernels, i.e. a finite sum of separable functions, which may be seen as a blockwise low-rank approximation of the system matrix. The blockwise approximant permits a fast matrix-vector multiplication, which can be exploited in iterative solvers, and can be stored efficiently. In contrast to the methods mentioned we will generate [2] the low-rank approximant from the matrix itself using only few entries and without using any explicit a priori known degenerate-kernel approximation. Special emphasis is put on the handling of symmetry conditions in connection with ACA. The feasibility of the proposed method is demonstrated by means of a numerical example.     

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.     

An adaptive dual-information FMBEM for 3D elasticity and its GPU implementation

Combined the boundary element method (BEM) with the fast multipole method (FMM), the fast multipole BEM (FMBEM) is proposed to solve large scale problems. A key issue the FMBEM has to address is the element integrals, which usually consumes much time when the FMM for N-body problems is directly used. In order to accelerate element integrals, we present an adaptive FMBEM with a particular dual-information tree structure which contains both node and element information, and use it for 3D elasticity in this paper. In our adaptive FMBEM, the Multipole Expansions (ME), Moment-to-Local (M2L) translation, Local Expansions (LE), and the Near Field Direct Computation (NFDC) are level independent so that they are suitable for parallel computing. The examples show that the time of ME and NFDC in our FMBEM is almost 1/3 and 1/2 compared with that in a node-based FMBEM which deals with FMBEM in a particle interaction mode. We develop two GPU parallel strategies to accelerate the processes of ME, M2L and NFDC and implement them on a NVIDIA GTX 285 GPU, and the speedups to an Intel Core2 Q9550 CPU using 4 cores can reach 10.7 for ME, 16.2 for M2L, and 3.6 for NFDC.     

Fast multipole DBEM analysis of fatigue crack growth

A fast multipole method (FMM) based on complex Taylor series expansions is applied to the dual boundary element method (DBEM) for large-scale crack analysis in linear elastic fracture mechanics. Combining multipole expansions with local expansions, both the computational complexity and memory requirement are reduced to O(N), where N is the number of DOF. An incremental crack-extension analysis based on the maximum principal stress criterion and the Paris law is used to simulate the fatigue growth of numerous cracks in a 2D solid. Some examples are presented to validate the numerical scheme.     

A wideband fast multipole accelerated boundary integral equation method for time‐harmonic elastodynamics in two dimensions

This article presents a wideband fast multipole method (FMM) to accelerate the boundary integral equation method for two‐dimensional elastodynamics in frequency domain. The present wideband FMM is established by coupling the low‐frequency FMM and the high‐frequency FMM that are formulated on the ingenious decomposition of the elastodynamic fundamental solution developed by Nishimura's group. For each of the two FMMs, we estimated the approximation parameters, that is, the expansion order for the low‐frequency FMM and the quadrature order for the high‐frequency FMM according to the requested accuracy, considering the coexistence of the derivatives of the Helmholtz kernels for the longitudinal and transcendental waves in the Burton–Muller type boundary integral equation of interest. In the numerical tests, the error resulting from the fast multipole approximation was monotonically decreased as the requested accuracy level was raised. Also, the computational complexity of the present fast boundary integral equation method agreed with the theory, that is, Nlog N, where N is the number of boundary elements in a series of scattering problems. The present fast boundary integral equation method is promising for simulations of the elastic systems with subwavelength structures. As an example, the wave propagation along a waveguide fabricated in a finite‐size phononic crystal was demonstrated. Copyright © 2012 John Wiley & Sons, Ltd.     

Application of the multi-level time-harmonic fast multipole BEM to 3-D visco-elastodynamics

This article extends previous work by the authors on the single- and multi-domain time-harmonic elastodynamic multi-level fast multipole BEM formulations to the case of weakly dissipative viscoelastic media. The underlying boundary integral equation and fast multipole formulations are formally identical to that of elastodynamics, except that the wavenumbers are complex-valued due to attenuation. Attention is focused on evaluating the multipole decomposition of the viscoelastodynamic fundamental solution. A damping-dependent modification of the selection rule for the multipole truncation parameter, required by the presence of complex wavenumbers, is proposed. It is empirically adjusted so as to maintain a constant accuracy over the damping range of interest in the approximation of the fundamental solution, and validated on numerical tests focusing on the evaluation of the latter. The proposed modification is then assessed on 3D single-region and multi-region visco-elastodynamic examples for which exact solutions are known. Finally, the multi-region formulation is applied to the problem of a wave propagating in a semi-infinite medium with a lossy semi-spherical inclusion (seismic wave in alluvial basin). These examples involve problem sizes of up to about 3×10⁵ boundary unknowns.     

Analysis of Solids with Numerous Microcracks Using the Fast Multipole DBEM

The fast multipole method (FMM) is applied to the dual boundary element method (DBEM) for the analysis of finite solids with large numbers of microcracks. The application of FMM significantly enhances the run-time and memory storage efficiency. Combining multipole expansions with local expansions, computational complexity and memory requirement are both reduced to O(N), where N is the number of DOFs (degrees of freedom). This numerical scheme is used to compute the effective in-plane bulk modulus of 2D solids with thousands of randomly distributed microcracks. The results prove that the IDD method, the differential method, and the method proposed by Feng and Yu can give proper estimates. The effect of microcrack non-uniform distribution is evaluated, and the numerical results show that non-uniform distribution of microcracks increases the effective in-plane bulk modulus of the whole microcracked solid.     

Adaptive cross approximation of tensors arising in the discretization of boundary integral operator shape derivatives

The shape derivative of a dense N×N BEM matrix is a sparse three-way tensor with O(N²) non-zero entries, to which standard BEM acceleration techniques such as the adaptive cross approximation (ACA) and FMM cannot be directly applied. The tensor can be used to compute shape sensitivities, or via adjoint equations, the gradient of an objective function. Although for many PDEs, calculation of the tensor can be avoided by expressing the shape derivative of the solution as the solution of a related PDE, this approach is not always easily amenable to BEM. Therefore, the computation of shape derivatives via the sparse three-way tensor is a valuable alternative, provided that efficient acceleration techniques exist. We propose a new algorithm for the approximation of BEM shape derivative tensors based on ACA that achieves the same complexity and error bounds as ACA for the BEM matrix itself. Numerical examples show that despite the much larger amount of data involved, the tensor approximation is only moderately slower than the matrix approximation. We also demonstrate the method on a shape optimization problem from the literature.     

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.     

A fast solution method for three-dimensional many-particle problems of linear elasticity

A boundary element method for solving three-dimensional linear elasticity problems that involve a large number of particles embedded in a binder is introduced. The proposed method relies on an iterative solution strategy in which matrix–vector multiplication is performed with the fast multipole method. As a result the method is capable of solving problems with N unknowns using only 𝒪(N) memory and 𝒪(N) operations. Results are given for problems with hundreds of particles in which N=𝒪(10⁵). © 1998 John Wiley & Sons, Ltd.     

On the preconditioners for fast multipole boundary element methods for 2D multi-domain elastostatics

Fast multipole method (FMM) has been successfully applied to accelerate the numerical solvers of boundary element method (BEM). However, the coefficient matrix implicitly formed by using FMM is sometimes ill-conditioned in cases when mixed boundary conditions exist, resulting in poor rate of convergence for iteration. So preconditioning is a critical part in the development of efficient FMM solver for BEM. In this paper, preconditioners based on sparse approximate inverse type are used for fast multipole BEM to deal with 2D elastostatics. Several sparsity patterns of the preconditioner are considered for single- and multi-domain problems, especially for 2D elastic body with large number of inclusions or cracks. Algorithms and cost analysis of preconditioning under different prescribed sparsity patterns are discussed. GMRES is used as the iterative solver. Numerical results show this type of preconditioner achieves satisfactory rate of convergence for fast multipole BEM and performs well for problems of fairly large sizes.     

A spectral multipole method for efficient solution of large-scale boundary element models in elastostatics

In this paper we introduce a method to reduce the solution cost for Boundary Element (BE) models from O(N³)operations to O(N²logN) operations (where N is the number of elements in the model). Previous attempts to achieve such an improvement in efficiency have been restricted in their applicability to problems with regular geometries defined on a uniform mesh. We have developed the Spectral Multipole Method (SMM) which can be used not only for problems with arbitrary geometries but also with a variety of element types. The memory necessary to store the required influence coefficients for the spectral multipole method is O(N) whereas the memory required for the traditional Boundary Element method is O(N²). We demonstrate the savings in computational speed and fast memory requirements in some numerical examples. We have established that the break-even point for the method can be as low as 500 elements, which implies that the method is not only suitable for extremely large-scale problems, but that it also provides a useful bridge between the small-scale and large-scale problems. We also demonstrate the performance of the multipole algorithm on the solution of large-scale granular assembly models. The large-scale BE capacity provided by this algorithm will not only prove to be useful in large macroscopic models but it will also make it possible to model microscopic damage processes that form the fundamental mechanisms in plastic flow and brittle fracture.     

A precorrected-FFT higher-order boundary element method for wave-body problems

The boundary element method (BEM) has been widely applied in the field of wave interaction with offshore structures, but it is still not easy to use in resolving large-scale problems because of computing costs and computer storage being increased by O(N²) for the traditional BEM. In this paper a precorrected Fast Fourier Transform (pFFT) higher-order boundary element method (HOBEM) is proposed for reducing the computational time and computer memory by O(N). By using a free-surface Green function for infinite water-depth, the disadvantage of the Fast Multipole Boundary Element Method (FMBEM)—i.e. unable to solve infinite deep-water wave problems—can be overcome. Numerical results from the problems of wave interaction with single- and multi-bodies show that the present method evidently has more advantages in saving memory and computing time, especially for large-scale problems, than the traditional HOBEM. In addition, the optimal variable of pFFT mesh is recommended to minimize time cost.     

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.     

A multiwavelet Galerkin boundary element method for the stationary Stokes problem in 3D

In this paper, a multiwavelet Galerkin boundary element method is presented for the fast solution of the stationary Stokes problem in three dimensions. Piecewise linear discontinuous multiwavelet bases are constructed on each patch of piecewise smooth surface individually, which allow easy and efficient evaluation of the matrix entries. Because of the use of the multiwavelets, the system matrix can be compressed to O (N) (N denotes the number of unknowns) nonzero entries without compromising the order of convergence as for the conventional Galerkin boundary element method. Numerical results of two test samples are given to demonstrate the availability of the present method.