Application of fast multipole Galerkin boundary integral equation method to elastostatic crack problems in 3D

Fast multipole method (FMM) has been developed as a technique to reduce the computational cost and memory requirements in solving large‐scale problems. This paper discusses an application of FMM to three‐dimensional boundary integral equation method for elastostatic crack problems. The boundary integral equation for many crack problems is discretized with FMM and Galerkin's method. The resulting algebraic equation is solved with generalized minimum residual method (GMRES). The numerical results show that FMM is more efficient than conventional methods when the number of unknowns is more than about 1200 and, therefore, can be useful in large‐scale analyses of fracture mechanics. Copyright © 2001 John Wiley & Sons, Ltd.     

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.     

An FMM for periodic boundary value problems for cracks for Helmholtz' equation in 2D

This paper presents an FMM (fast multipole method) for periodic boundary value problems for Helmholtz' equation in 2D. The periodic Green function is an important ingredient in our formulation, which is computed efficiently with the help of the Fourier analysis. We validate the proposed method by comparing the obtained numerical results with those computed with the conventional approach. We then apply the proposed method to the analysis of scattering problems for periodic array of cracks and plot the energy transmittance vs wave numbers. The stopband and related phenomena are observed clearly. Copyright © 2007 John Wiley & Sons, Ltd.     

An application of fast multipole method in analyzing acoustic filters

Abstract

The purpose of this study is to investigate the acoustic performance of mufflers. As a numerical scheme for analyzing an acoustic filter, the boundary element method is more suitable than are domain methods, such as the finite element method, which has to mesh the domain. However, the coefficient matrices established by the boundary element method are full and often non‐symmetrical. In order to decrease the computational time required, the fast multipole method has been applied. The fast multipole method, when compared with the boundary element method, reduces CPU time from an order of N² to Nlog^γ N, where N is the number of unknowns and γ is a constant. This study focused on the different geometries of plates within simple expansion acoustic filters. Numerical analysis demonstrates that the transmission loss at a particular frequency performance is better when employing a simple expansion acoustic filter with plates.     

The hybrid boundary node method accelerated by fast multipole expansion technique for 3D potential problems

This paper presents a fast formulation of the hybrid boundary node method (Hybrid BNM) for solving problems governed by Laplace's equation in 3D. The preconditioned GMRES is employed for solving the resulting system of equations. At each iteration step of the GMRES, the matrix–vector multiplication is accelerated by the fast multipole method. Green's kernel function is expanded in terms of spherical harmonic series. An oct‐tree data structure is used to hierarchically subdivide the computational domain into well‐separated cells and to invoke the multipole expansion approximation. Formulations for the local and multipole expansions, and also conversion of multipole to local expansion are given. And a binary tree data structure is applied to accelerate the moving least square approximation on surfaces. All the formulations are implemented in a computer code written in C++. Numerical examples demonstrate the accuracy and efficiency of the proposed approach. Copyright © 2005 John Wiley & Sons, Ltd.     

A fast multipole boundary integral equation method for crack problems in 3D

This paper discusses a three-dimensional fast multipole boundary integral equation method for crack problems for Laplace's equation. The proposed implementation uses collocation and piecewise constant shape functions to discretise the hypersingular boundary integral equation for crack problems. The resulting numerical equation is solved with GMRES (generalised minimum residual method) in connection with FMM (fast multipole method). It is found that the obtained code is faster than a conventional one when the number of unknowns is greater than about 1300.     

hp Fast multipole boundary element method for 3D acoustics

A fast multipole boundary element method (FMBEM) extended by an adaptive mesh refinement algorithm for solving acoustic problems in three‐dimensional space is presented in this paper. The Collocation method is used, and the Burton–Miller formulation is employed to overcome the fictitious eigenfrequencies arising for exterior domain problems. Because of the application of the combined integral equation, the developed FMBEM is feasible for all positive wave numbers even up to high frequencies. In order to evaluate the hypersingular integral resulting from the Burton–Miller formulation of the boundary integral equation, an integration technique for arbitrary element order is applied. The fast multipole method combined with an arbitrary order h‐p mesh refinement strategy enables accurate computation of large‐scale systems. Numerical examples substantiate the high accuracy attainable by the developed FMBEM, while requiring only moderate computational effort at the same time. Copyright © 2016 John Wiley & Sons, Ltd.     

A fast collocation method for an inverse boundary value problem

In this paper, we present an implementation of a fast multiscale collocation method for boundary integral equations of the second kind, and its application to solving an inverse boundary value problem of recovering a coefficient function from a boundary measurement. We illustrate by numerical examples the insensitive nature of the map from the coefficient to measurement, and design and test a Gauss–Newton iteration algorithm for obtaining the best estimate of the unknown coefficient from the given measurement based on a least‐squares formulation. Copyright © 2004 John Wiley & Sons, Ltd.     

Optimizing the multipole‐to‐local operator in the fast multipole method for graphical processing units

This paper presents a number of algorithms to run the fast multipole method (FMM) on NVIDIA CUDA‐capable graphical processing units (GPUs) (Nvidia Corporation, Sta. Clara, CA, USA). The FMM is a class of methods to compute pairwise interactions between N particles for a given error tolerance and with computational cost of . The methods described in the paper are applicable to any FMMs in which the multipole‐to‐local (M2L) operator is a dense matrix and the matrix is precomputed. This is the case for example in the black‐box fast multipole method (bbFMM), which is a variant of the FMM that can handle large class of kernels. This example will be used in our benchmarks. In the FMM, two operators represent most of the computational cost, and an optimal implementation typically tries to balance those two operators. One is the nearby interaction calculation (direct sum calculation, line 29 in Listing 1), and the other is the M2L operation. We focus on the M2L. By combining multiple M2L operations and reordering the primitive loops of the M2L so that CUDA threads can reuse or share common data, these approaches reduce the movement of data in the GPU. Because memory bandwidth is the primary bottleneck of these methods, significant performance improvements are realized. Four M2L schemes are detailed and analyzed in the case of a uniform tree. The four schemes are tested and compared with an optimized, OpenMP parallelized, multi‐core CPU code. We consider high and low precision calculations by varying the number of Chebyshev nodes used in the bbFMM. The accuracy of the GPU codes is found to be satisfactory and achieved performance over 200 Gflop/s on one NVIDIA Tesla C1060 GPU (Nvidia Corporation, Sta. Clara, CA, USA). This was compared against two quad‐core Intel Xeon E5345 processors (Intel Corporation, Sta. Clara, CA, USA) running at 2.33 GHz, for a combined peak performance of 149 Gflop/s for single precision. For the low FMM accuracy case, the observed performance of the CPU code was 37 Gflop/s, whereas for the high FMM accuracy case, the performance was about 8.5 Gflop/s, most likely because of a higher frequency of cache misses. We also present benchmarks on an NVIDIA C2050 GPU (a Fermi processor)(Nvidia Corporation, Sta. Clara, CA, USA) in single and double precision. Copyright © 2011 John Wiley & Sons, Ltd.     

A fast multipole boundary element method for solving the thin plate bending problem

A fast multipole boundary element method (BEM) for solving large-scale thin plate bending problems is presented in this paper. The method is based on the Kirchhoff thin plate bending theory and the biharmonic equation governing the deflection of the plate. First, the direct boundary integral equations and the conventional BEM for thin plate bending problems are reviewed. Second, the complex notation of the kernel functions, expansions and translations in the fast multipole BEM are presented. Finally, a few numerical examples are presented to show the accuracy and efficiency of the fast multipole BEM in solving thin plate bending problems. The bending rigidity of a perforated plate is evaluated using the developed code. It is shown that the fast multipole BEM can be applied to solve plate bending problems with good accuracy. Possible improvements in the efficiency of the method are discussed.     

Application of new fast multipole boundary integral equation method to crack problems in 3D

Fast multipole method (FMM) has been developed as a technique to reduce the computational cost and memory requirements in solving large scale problems. This paper discusses an application of the new version of FMM to three-dimensional boundary integral equation method (BIEM) for crack problems for the Laplace equation. The boundary integral equation is discretised with collocation method. The resulting algebraic equation is solved with generalised minimum residual method (GMRES). The numerical results show that the new version of FMM is more efficient than the original FMM.     

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.     

A fast boundary cloud method for 3D exterior electrostatic analysis

An accelerated boundary cloud method (BCM) for boundary‐only analysis of 3D electrostatic problems is presented here. BCM uses scattered points unlike the classical boundary element method (BEM) which uses boundary elements to discretize the surface of the conductors. BCM combines the weighted least‐squares approach for the construction of approximation functions with a boundary integral formulation for the governing equations. A linear base interpolating polynomial that can vary from cloud to cloud is employed. The boundary integrals are computed by using a cell structure and different schemes have been used to evaluate the weakly singular and non‐singular integrals. A singular value decomposition (SVD) based acceleration technique is employed to solve the dense linear system of equations arising in BCM. The performance of BCM is compared with BEM for several 3D examples. Copyright © 2004 John Wiley & Sons, Ltd.     

Application of symmetric indirect Trefftz method to free vibration problems in 2D

A symmetric indirect Trefftz method is developed to solve the free vibration problem of a 2D membrane. It is proved that in this approach the spurious eigensolution exists, and an auxiliary matrix is constructed to help extraction of the spurious solution using the generalized singular‐value decomposition. In addition to the spurious eigensolution, this regular formulation suffers from its ill‐posed nature, i.e. the numerical instability. In order to deal with the numerical instability, the Tikhonov's regularization method, in conjunction with the generalized singular‐value decomposition, is suggested. The proposed approach has some merits when compared with other regular boundary element formulations reported so far; namely the capacity of representing eigenmodes and the ability to deal with a multiply connected domain of genus 1. Several numerical examples are demonstrated to show the validity of the current approach. Copyright © 2003 John Wiley & Sons, Ltd.     

A fast boundary cloud method for exterior 2D electrostatic analysis

An accelerated boundary cloud method (BCM) for boundary‐only analysis of exterior electrostatic problems is presented in this paper. The BCM uses scattered points instead of the classical boundary elements to discretize the surface of the conductors. The dense linear system of equations generated by the BCM are solved by a GMRES iterative solver combined with a singular value decomposition based rapid matrix–vector multiplication technique. The accelerated technique takes advantage of the fact that the integral equation kernel (2D Green's function in our case) is locally smooth and, therefore, can be dramatically compressed by using a singular value decomposition technique. The acceleration technique greatly speeds up the solution phase of the linear system by accelerating the computation of the dense matrix–vector product and reducing the storage required by the BCM. Copyright © 2002 John Wiley & Sons, Ltd.     

A fast dual boundary element method for 3D anisotropic crack problems

In the present paper a fast solver for dual boundary element analysis of 3D anisotropic crack problems is formulated, implemented and tested. The fast solver is based on the use of hierarchical matrices for the representation of the collocation matrix. The admissible low rank blocks are computed by adaptive cross approximation (ACA). The performance of ACA against the accuracy of the adopted computational scheme for the evaluation of the anisotropic kernels is investigated, focusing on the balance between the kernel representation accuracy and the accuracy required for ACA. The system solution is computed by a preconditioned GMRES and the preconditioner is built exploiting the hierarchical arithmetic and taking full advantage of the hierarchical format. The effectiveness of the proposed technique for anisotropic crack problems has been numerically demonstrated, highlighting the accuracy as well as the significant reduction in memory storage and analysis time. In particular, it has been numerically shown that the computational cost grows almost linearly with the number of degrees of freedom, obtaining up to solution speedups of order 10 for systems of order 10⁴. Moreover, the sensitivity of the performance of the numerical scheme to materials with different degrees of anisotropy has been assessed. Copyright © 2009 John Wiley & Sons, Ltd.     

A parallel fast multipole accelerated integral equation scheme for 3D Stokes equations

In this paper, we discuss a numerical scheme for the Stokes equations in three dimensions. It uses an integral equation formulation and is accelerated by the new version of fast multipole method first introduced by Greengard and Rokhlin in 1997 (Acta Numerica 1997; 6 :229–269). The code is parallelized to solve problems of extremely large size. The resulting numerical solver can be applied to Stokes flows in complex geometry and also serves as a building block for solving the Navier–Stokes equations of low to moderate Reynold's numbers. Copyright © 2006 John Wiley & Sons, Ltd.     

A wideband fast multipole algorithm for two‐dimensional volume integral equations

This paper describes a wideband fast multipole algorithm (FMA) for the computation of two‐dimensional volume integral equations. Our previous paper presented the wideband FMA by switching between the diagonal and non‐diagonal forms according to cell size and required accuracy. In order to improve the efficiency of the algorithm, we use interpolation and filtering techniques. Moreover, we introduce a simple and efficient way to store sequences of the special functions and their discrete Fourier transforms. Numerical examples show that the computational and memory complexities are reduced from O(N²) to O(N), where N is the number of square elements followed by the discretization of the volume integral equations. The computation results show very good agreement with the analytical solutions. We present some numerical results for the computation of scattering from a cylindrical object with sharp edges and a Gaussian‐like inhomogeneous cylinder. Copyright © 2008 John Wiley & Sons, Ltd.     

Boundary value problems of elastodynamics under stationary moving forces using boundary integral equation method

The boundary value problem of elastodynamics is considered in cylindrical domains when acting boundary forces are moving with constant speed parallel to cylinder's axis. The fundamental solutions, boundary integral equations and integral representation of the solutions are constructed using distribution theory for three kinds of speed: subsonic, transonic and supersonic.     

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.