Fast multipole method based solution of electrostatic and magnetostatic field problems

Abstact Applications of boundary element methods (BEM) to the solution of static field problems in electrical engineering are considered in this paper. The choice of a suitable BEM formulation for electrostatics, steady current flow fields or magnetostatics is discussed from user's point of view. The dense BEM matrix is compressed with an enhanced fast multipole method (FMM) which combines well-known BEM techniques with the FMM approach. An adaptive grouping scheme for problem oriented meshes is presented along with a discussion on the influence of the mesh to the efficiency of the FMM. The computational costs of the FMM algorithm are analyzed for typical problems in practice. Finally, some electrostatic and magnetostatic numerical examples demonstrate the simple usability and the efficiency of the FMM. Communicated by: U. Langer     

A fast quasi-multiple medium method for 3-D bem calculation of parasitic capacitance

A quasi-multiple medium (QMM) method is proposed to accelerate the boundary element method (BEM) for the 3-D parasitic capacitance calculation. In the QMM method, a homogeneous dielectric is decomposed into a number of fictitious medium blocks, each with the same permittivity of original medium. By the localization character of BEM, the QMM method makes great sparsity to the coefficient matrix of the overall discretized BEM equations. Then, using storing technique of sparse matrix and iterative equation solvers, the sparsity is explored to greatly reduce CPU time and memory usage of BEM computation. The computational complexity of the QMM accelerated BEM for a single-medium model problem is analyzed, and it is concluded as O(N), if the number of iterations is bounded. Numerical results verify the theoretical analysis and show the accelerating efficiency of the QMM method for calculation of 3-D parasitic capacitance.     

Comparison of FEM and BEM for interactive object simulation

There are two major approaches for real-time object simulation namely, the geometry (non-physically) based and the physically based approaches. Geometry based approaches such as free-form deformation (FFD) employ purely geometric techniques to model deformation. Physically based approaches usually adopt mass-spring system, finite element method (FEM) or boundary element method (BEM) for simulation. The mass-spring system is simple and only gives a coarse estimation of object deformation. Recently, FEM and BEM have been extensively used in object simulation because of the demand for more realistic simulation. However, a major drawback of FEM and BEM is their difficulty to achieve real-time deformation. In this article, we compare two different physically based approaches, FEM and BEM, according to their accuracy and computational complexity. Several experiments were conducted to compare the time required for the pre-computation process and the deformation process. In addition, the BEM with linear boundary elements is implemented and tested. At the current state of investigation, for the meshes with triangular elements, BEM with linear boundary elements is significantly faster than BEM with constant boundary elements under most of the circumstances. With the band matrix of FEM, the pre-computation process is faster than the BEM for a model with small mesh size. However if the mesh size of the model is large, the pre-computation process of BEM with linear boundary elements is the fastest.     

求解二维随机多区域声波散射问题的快速多极边界元方法

快速多极算法(FMM)是求解大尺度边界元问题的一种很有效的快速算法.应用快速多极算法求解二维随机多区域声散射问题的边界积分方程.首先给出了求解该问题的边界积分方程,进而给出快速多极算法求解的算法实现过程以及积分算子的相应多极展开、局部展开和相应系数的转化关系式.最后通过对数值例子的计算表明快速多极算法在求解随机多区域声散射问题时的可行性及高效性,其求解存储量和计算量都是O(N).     

A new fast multipole boundary element method for two dimensional acoustic problems

A new fast multipole boundary element method (BEM) is presented in this paper for solving large-scale two dimensional (2D) acoustic problems based on the improved Burton–Miller formulation. This algorithm has several important improvements. The fast multipole BEM employs the improved Burton–Miller formulation, and successfully overcomes the non-uniqueness difficulty associated with the conventional BEM for exterior acoustic problems. 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. Furthermore, the fast multipole method (FMM) and the approximate inverse preconditioned generalized minimum residual method (GMRES) iterative solver are adopted to greatly improve the overall computational efficiency. The numerical examples with Neumann boundary conditions are presented that clearly demonstrate the accuracy and efficiency of the developed fast multipole BEM for solving large-scale 2D acoustic problems in a wide range of frequencies.     

Improvement of the accuracy in boundary element method based on high-order discretization

The boundary element method (BEM) is a popular method to solve various problems in engineering and physics and has been used widely in the last two decades. In high-order discretization the boundary elements are interpolated with some polynomial functions. These polynomials are employed to provide higher degrees of continuity for the geometry of boundary elements, and also they are used as interpolation functions for the variables located on the boundary elements. The main aim of this paper is to improve the accuracy of the high-order discretization in the two-dimensional BEM. In the high-order discretization, both the geometry and the variables of the boundary elements are interpolated with the polynomial function P_m, where m denotes the degree of the polynomial. In the current paper we will prove that if the geometry of the boundary elements is interpolated with the polynomial function P_m+1 instead of P_m, the accuracy of the results increases significantly. The analytical results presented in this work show that employing the new approach, the order of convergence increases from O(L₀)^m to O(L₀)^m+1 without using more CPU time where L₀ is the length of the longest boundary element. The theoretical results are also confirmed by some numerical experiments.     

Parallelization of the FMM on distributed-memory GPGPU systems for acoustic-scattering prediction

In this work, we carry out the parallelization of the single level Fast Multipole Method (FMM) for solving acoustic-scattering problems (using the Helmholtz equation) on distributed-memory GPGPU systems. With the aim of enlarging the scope of feasible simulations, the presented solution combines the techniques developed for our distributed-memory CPU solver with our shared-memory GPGPU solver. The performance of the developed solution is proved using two different GPGPU clusters: the first one consists of two workstations with NVIDIA GTX 480 GPUs linked by a Gigabit Ethernet network, and the second one comprises four nodes with NVIDIA Tesla M2090 GPUs linked by an Infiniband network.     

Acoustic scattering solver based on single level FMM for multi-GPU systems

In this paper, we present a heterogeneous parallel solver of a high frequency single level Fast Multipole Method (FMM) for the Helmholtz equation applied to acoustic scattering. The developed solution uses multiple GPUs to tackle the compute bound steps of the FMM (aggregation, disaggregation, and near interactions) while the CPU handles a memory bound step (translation) using OpenMP. The proposed solver performance is measured on a workstation with two GPUs (NVIDIA GTX 480) and is compared with that of a distributed memory solver run on a cluster of 32 nodes (HP BL465c) with an Infiniband network. Some energy efficiency results are also presented in this work.     

Analysis of three-dimensional anisotropic heat conduction problems on thin domains using an advanced boundary element method

In this paper, an advanced boundary element method (BEM) is developed for solving three-dimensional (3D) anisotropic heat conduction problems in thin-walled structures. The troublesome nearly singular integrals, which are crucial in the applications of the BEM to thin structures, are calculated efficiently by using a nonlinear coordinate transformation method. For the test problems studied, promising BEM results with only a small number of boundary elements have been obtained when the thickness of the structure is in the orders of micro-scales (10^?6), which is sufficient for modeling most thin-walled structures as used in, for example, smart materials and thin layered coating systems. The advantages, disadvantages as well as potential applications of the proposed method, as compared with the finite element method (FEM), are also discussed.     

The application of boundary element method to the resistance calculation problem in designing flat panel displays

Several techniques are presented for the efficient resistance calculation of wiring structures in flat panel display (FPD). The techniques are based on two‐dimensional boundary element method (BEM), suitable for the geometry characteristics of the FPD structures. With an automatic strategy for boundary element partition and the analytical BEM‐coupled approach, the proposed resistance solver shows good accuracy and fast computational speed. Numerical experiments demonstrate that the solver can be more than 10,000 times faster than the finite difference solver raphael while preserving good accuracy. And the proposed techniques accelerate the original BEM remarkably. Structures from real FPD designs have validated the efficiency of the proposed techniques.     

Structural shape optimisation using boundary elements and the biological growth method

A numerical evolutionary procedure for the structural optimisation for stress reduction of two-dimensional structures is presented in this paper. The proposed procedure couples the biological growth method (BGM) with the boundary element method (BEM). The boundary-only intrinsic characteristic of BEM together with its accuracy in the boundary displacement and stress solutions make BEM especially attractive for solving shape-optimisation problems. Two formulations of BEM are used in this work: the standard for two-dimensional elastostatics for the stress analysis and the dual reciprocity method (DRM), which is used to model the swelling or shrinking of the material. Two examples are analysed to illustrate the proposed methodology and to demonstrate its versatility and robustness.     

并行计算水下大尺度弹性壳体的低频声散射

有限元与边界元耦合模型是研究水下弹性壳体目标低频声散射常用的数值方法。应用该模型计算大尺度弹性目标的声散射时需要大量的计算时间与存储空间,采用并行数值的方式可以解决这一问题。首先并行计算生成有限元矩阵和边界元矩阵,然后应用并行化的广义极小残差(GMRES)迭代算法求解大型非对称线性方程组。详细叙述了并行GMRES(m)迭代算法的执行过程,并以球壳的声散射计算为例分析了迭代步数对算法收敛情况的影响。最后计算了Benchmark目标模型的低频散射声场,分析了其收发分置散射目标强度以及表面声场的分布。     

子结构方法在汽车约束系统固定点强度模拟中的应用

子结构方法是有限元仿真中只关注局部模型物理特性的一种重要的简化计算方法。它通过读取初始模型定义的子结构单元节点信息实现对整体模型的简化。通过这种简化可以节省大量的建模时间和计算时间,从而提高计算效率。本文介绍了子结构方法的基本原理和使用Pam-crash解算器的计算流程,并通过实例介绍了子结构方法在汽车约束系统固定点强度模拟中的应用,验证了该方法在汽车开发的实际仿真计算工况中的可行性和准确性。     

Analysis of thin piezoelectric solids by the boundary element method

The piezoelectric boundary integral equation (BIE) formulation is applied to analyze thin piezoelectric solids, such as thin piezoelectric films and coatings, using the boundary element method (BEM). The nearly singular integrals existing in the piezoelectric BIE as applied to thin piezoelectric solids are addressed for the 2-D case. An efficient analytical method to deal with the nearly singular integrals in the piezoelectric BIE is developed to accurately compute these integrals in the piezoelectric BEM, no matter how close the source point is to the element of integration. Promising BEM results with only a small number of elements are obtained for thin films and coatings with the thickness-to-length ratio as small as 10⁻⁶, which is sufficient for modeling many thin piezoelectric films as used in smart materials and micro-electro-mechanical systems.     

A real-time multigrid finite hexahedra method for elasticity simulation using CUDA

We present a multigrid approach for simulating elastic deformable objects in real time on recent NVIDIA GPU architectures. To accurately simulate large deformations we consider the co-rotated strain formulation. Our method is based on a finite element discretization of the deformable object using hexahedra. It draws upon recent work on multigrid schemes for the efficient numerical solution of partial differential equations on such discretizations. Due to the regular shape of the numerical stencil induced by the hexahedral regime, and since we use matrix-free formulations of all multigrid steps, computations and data layout can be restructured to avoid execution divergence of parallel running threads and to enable coalescing of memory accesses into single memory transactions. This enables to effectively exploit the GPU’s parallel processing units and high memory bandwidth via the CUDA parallel programming API. We demonstrate performance gains of up to a factor of 27 and 4 compared to a highly optimized CPU implementation on a single CPU core and 8 CPU cores, respectively. For hexahedral models consisting of as many as 269,000 elements our approach achieves physics-based simulation at 11 time steps per second.     

舰船水下声场边界元法建模与计算机模拟

根据舰船声场的特性,将舰船水下声场简化为一特殊的半自由空间声辐射问题,利用边界元法(BEM)建立了舰船水下声场的数值计算模型。通过对声场边界条件的计算机仿真和计算,获得了部分计算结果。结果表明:由所建模型计算的舰船辐射声场与真实海域中的实测规律基本吻合,该文提出的方法是有效可行的。最后对存在的问题进行了讨论。     

Lead field computation for the electrocardiographic inverse problem--finite elements versus boundary elements

In order to be able to solve the inverse problem of electrocardiography, the lead field matrix (transfer matrix) has to be calculated. The two methods applied for computing this matrix, which are compared in this study, are the boundary element method (BEM) and the finite element method (FEM). The performance of both methods using a spherical model was investigated. For a comparable discretization level, the BEM yields smaller relative errors compared to analytical solutions. The BEM needs less computation time, but a larger amount of memory. Inversely calculated myocardial activation times using either the FEM or BEM computed lead field matrices give similar activation time patterns. The FEM, however, is also capable of considering anisotropic conductivities. This property might have an impact for future development, when also individual myocardial fiber architecture can be considered in the inverse formulation.     

层次式直接边界元计算VLSI三维互连电容

文中将Ａｐｐｅｌ处理多体问题的层次式算法思想实现于直接边界元法,用以计算ＶＬＳＩ三维互连寄生电容。直接边界积分方程同时含有边界上的电势与法向电场强度,能比间接边界元法更方便地处理多介质及有限介质结构,直接边界元法的层次式计算涉及对三种边界（强加边界、自然边界与介质交界面）及两种积分核（１／ｒ与１／ｒ＾３）的处理,显著区别于基于间接边界元法、仅处理强加边界与一种分核的层次式算法。文中以边界元的层次划     

Quality based design approach for a single crystal silicon microactuator using DOE technique and response surface model

 This paper discusses the use of DOE technique and response surface model as an efficient quality based design approach to optimize coupled electromechanical behavior of a single crystal silicon micro-actuator for hard disk drives (HDD). A number of experiments for different settings of the microactuator parameters are planned and analyzed. The fitted response surface models are built using the regression technique. Finite element method (FEM), boundary element method (BEM) and optimization techniques are utilized to predict and verify the microactuator performance. Example results show that the proposed approach is effective to guide microactuator design to achieve a robust and reliable design in a most efficient way. Received: 5 July 2001/Accepted: 17 October 2001     

混合模型下FMM算法中近程计算的优化研究

为提高计算多体问题的效率,通过分析多体问题的典型算法FMM(fast multiple method)的计算特点,提出运用CPU和加速部件FPGA构成混合部件计算其近程作用的方案。重点研究混合计算模型上的近程计算特性和优化策略,从计算、通信和存储多方面分析近程计算,提出分层按块的数据准备策略,及在该策略中修改FMM空间编码方式,使近程计算更好地适应于混合模型,从而提高整个FMM算法的执行效率。实验结果表明了该数据准备策略和采用的空间编码方式的可行性和高效性。