Analysis of a Diagonal Form of the Fast Multipole Algorithm for Scattering Theory

Discretisation of the integral equations of acoustic scattering yields a system of linear equations with full coefficient matrices. In recent years a number of fast algorithms for the solution of this system have been proposed. In this paper we present a complete analysis for a fast multipole method for the Helmholtz equation. A one-level diagonal form of the multipole method is applied to a hypersingular integral equation arising from 2d scattering theory. The error of the approximation is analysed and the results used to establish the complexity of the method.     

多层快速多极子方法的快速插值

多层快速多极子方法(MLFMM)可用来加速迭代求解由Maxwell方程组或Helmholtz方程导出的积分方程,其复杂度理论上是O(NlogN),N为未知量个数.MLFMM依赖于快速计算每层的转移项,以及上聚和下推过程中的层间插值.本文引入计算类似N体问题的一维快速多极子方法(FMM1D).基于FMM1D的快速Lagr...     

The FMM accelerated PIES with the modified binary tree in solving potential problems for the domains with curvilinear boundaries

The paper presents an accelerating of solving potential boundary value problems (BVPs) with curvilinear boundaries by modified parametric integral equations system (PIES). The fast multipole method (FMM) known from the literature was included into modified PIES. To consider complex curvilinear shapes of a boundary, the modification of a binary tree used by the FMM is proposed. The FMM combined with the PIES, called the fast PIES, also allows a significant reduction of random access memory (RAM) utilization. Therefore, it is possible to solve complex engineering problems on a standard personal computer (PC). The proposed algorithm is based on the modified PIES and allows for obtaining accurate solutions of complex BVPs described by the curvilinear boundary at a reasonable time on the PC.

     

自适应快速多极正则化无网格法求解大规模三维位势问题

正则化无网格法（regularized meshless method, RMM）是一种新的边界型无网格数值离散方法．该方法克服了近年来引起广泛关注的基本解方法（method of fundamental solutions, MFS）的虚假边界缺陷,继承了其无网格、无数值积分、易实施等优点．另一方面,RMM方法同MFS方法的插值方程都涉及非对称稠密系数矩阵,运用常规代数方程的迭代法求解时都要求O(N2)量级的乘法计算量和存储量．随着问题自由度的增加,该方法的计算量增加极快,效率较低,一般难以计算大规模问题．为了克服这个缺点,利用对角形式的快速多级算法（fast multipole method, FMM）来加速RMM方法,发展了快速多级正则化无网格法（fast multipole regularized mesheless method, FM-RMM）．该方法无需数值积分并且具有O(N)量级的计算量和存储量,可有效地求解大规模工程问题．数值算例表明,FM-RMM算法可成功在内存为4GB的Core(TM)Ⅱ台式机上求解高达百万级自由度的三维位势问题．     

A fast multipole method for the evaluation of elastostatic fields in a half-space with zero normal stress

In this paper, we present a fast multipole method (FMM) for the half-space Green’s function in a homogeneous elastic half-space subject to zero normal stress, for which an explicit solution was given by Mindlin (Physics 7, 195–202 1936). The image structure of this Green’s function is unbounded, so that standard outgoing representations are not easily available. We introduce two such representations here, one involving an expansion in plane waves and one involving a modified multipole expansion. Both play a role in the FMM implementation.     

基于三维弹性问题的多极边界元法核函数分解

多极边界元法已经成功地应用于大规模工程计算中.得到并且证明了基于三维弹性问题的多极边界元法核函数分解的定理(定理1),完善了多击边界元法的数学理论.     

Higher-order quadratures for circulant preconditioned Wiener-Hopf equations

In this paper, we consider solving matrix systems arising from the discretization of Wiener-Hopf equations by preconditioned conjugate gradient (PCG) methods. Circulant integral operators as preconditioners have been proposed and studied. However, the discretization of these preconditioned equations by employing higher-order quadratures leads to matrix systems that cannot be solved efficiently by using fast Fourier transforms (FFTs). The aim of this paper is to propose new preconditioners for Wiener-Hopf equations. The discretization of these preconditioned operator equations by higher-order quadratures leads to matrix systems that involve only Toeplitz, circulant and diagonal matrix-vector multiplications and hence can be computed efficiently by FFTs in each iteration. We show that with the proper choice of kernel functions of Wiener-Hopf equations, the resulting preconditioned operators will have clustered spectra and therefore the PCG method converges very fast. Numerical examples are given to illustrate the fast convergence of the method and the improvement of the accuracy of the computed solutions with using higher-order quadratures.Research supported by the Cooperative Research Centre for Advanced Computational Systems.Research supported in part by Lee Ka Shing scholarship.     

Justification of the fast multipole method for the stokes system. Part II. Exterior domain problems

We consider the exterior domain problems of Dirichlet and Neumann type of the two-dimensional Stokes equations. For the solution of this boundary value problem we choose a potential ansatz and show that for the reduction of the computational costs, the fast multipole method of Greengard and Rokhlin can be used. Therefore, we find a complex representation of the hydrodynamical potentials and provide statements about the corresponding multipole and Taylor expansions, as well as the appropriate translation, rotation and conversion operators. The theoretical statements are illustrated by numerical experiments. Bibliography: 15 titles.     

The fast multipole method for the symmetric boundary integral formulation

^** Email: of{at}mathematik.uni-stuttgart.de^*** Email: o.steinbach{at}tugraz.at^**** Email: wendland{at}mathematik.uni-stuttgart.de A symmetric Galerkin boundary-element method is used for thesolution of boundary-value problems with mixed boundary conditionsof Dirichlet and Neumann type. As a model problem we considerthe Laplace equation. When an iterative scheme is employed forsolving the resulting linear system, the discrete boundary integraloperators are realized by the fast multipole method. While thesingle-layer potential can be implemented straightforwardlyas in the original algorithm for particle simulation, the double-layerpotential and its adjoint operator are approximated by the applicationof normal derivatives to the multipole series for the kernelof the single-layer potential. The Galerkin discretization ofthe hypersingular integral operator is reduced to the single-layerpotential via integration by parts. We finally present a correspondingstability and error analysis for these approximations by thefast multipole method of the boundary integral operators. Itis shown that the use of the fast multipole method does notharm the optimal asymptotic convergence. The resulting linearsystem is solved by a GMRES scheme which is preconditioned bythe use of hierarchical strategies as already employed in thefast multipole method. Our numerical examples are in agreementwith the theoretical results.     

多裂纹问题计算分析的本征COD边界积分方程方法

针对多裂纹问题，若采用常规的数值求解技术，计算效率较低.为实现多裂纹问题的大规模数值模拟，建立了本征裂纹张开位移（crack opening displacement, COD）边界积分方程及其迭代算法，并引入Eshelby矩阵的定义，将多裂纹分为近场裂纹和远场裂纹来处理裂纹间的相互影响.以采用常单元作为离散单元的快速多极边界元法为参照，对提出的计算模型和迭代算法进行了数值验证.结果表明，本征COD边界积分方程方法在处理多裂纹问题时取得较大的改进，其计算效率显著高于传统的边界元法和快速多极边界元法.     

The fast Fourier transform and the numerical solution of one-dimensional boundary integral equations

Summary Here we present a fully discretized projection method with Fourier series which is based on a modification of the fast Fourier transform. The method is applied to systems of integro-differential equations with the Cauchy kernel, boundary integral equations from the boundary element method and, more generally, to certain elliptic pseudodifferential equations on closed smooth curves. We use Gaussian quadratures on families of equidistant partitions combined with the fast Fourier transform. This yields an extremely accurate and fast numerical scheme. We present complete asymptotic error estimates including the quadrature errors. These are quasioptimal and of exponential order for analytic data. Numerical experiments for a scattering problem, the clamped plate and plane estatostatics confirm the theoretical convergence rates and show high accuracy.     

MULTILEVEL AUGMENTATION METHODS FOR SOLVING OPERATOR EQUATIONS

We introduce multilevel augmentation methods for solving operator equations based on direct sum decompositions of the range space of the operator and the solution space of the operator equation and a matrix splitting scheme. We establish a general setting for the analysis of these methods, showing that the methods yield approximate solutions of the same convergence order as the best approximation from the subspace. These augmentation methods allow us to develop fast, accurate and stable nonconventional numerical algorithms for solving operator equations. In particular, for second kind equations, special splitting techniques are proposed to develop such algorithms. These algorithms are then applied to solve the linear systems resulting from matrix compression schemes using wavelet-like functions for solving Fredholm integral equations of the second kind. For this special case, a complete analysis for computational complexity and convergence order is presented. Numerical examples are included to demonstra     

Fast iteration method in the problem of waves interacting with a set of thin screens

A new iteration method is proposed for the wave equation describing the scattering of a harmonic wave from an arbitrary configuration in the form of an array of thin straight barriers. The problem is reduced to a system of boundary integral equations, which are discretized by applying the Belotserkovskii-Lifanov method. In discrete form, a finite number of systems with Toeplitz matrices (the number of systems is equal to the number of barriers) are solved at each iteration step by applying special fast methods. The algorithm is tested on several geometries, and its convergence in these cases is analyzed.     

Wavelet compression of integral operators arising from boudary-domain integral method

The boundary-domain integral method uses Green's functions to write integral representations of partial differential equations. Since Green's functions are non-local, the systems of linear equations arising from the discretization of integral representations are fully populated. Several algorithms have been proposed, which yield a data-sparse approximation of these systems, such as the fast multipole method, adaptive cross approximation and among others, wavelet compression. In the framework of solving the Navier-Stokes equations in velocity-vorticity form one may utilize the boundary-domain integral method for the solution of the kinematics equation to calculate the boundary vorticity values. Since the kinematics equation is a Poisson type equation, usually its integral representation is written with the Green's function for the Laplace operator. In this work, we introduce a false time into the equation and parabolize its nature. Thus, a time-dependent Green's function may be used. This provides a new parameter, the time step, which can be set to control the Green's function. The time-dependent Green's function is a global function, but by carefully choosing the time step, its behaviour is almost local. This makes it a good candidate for wavelet compression, yielding much better compression ratios at a given accuracy than when using the Green's function for the Laplace operator. However, as false time is introduced, several time steps must be solved in order to reach a converged solution. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Second-kind integral equations for the Laplace-Beltrami problem on surfaces in three dimensions

The Laplace-Beltrami problem Δ_Γψ = f has several applications in mathematical physics, differential geometry, machine learning, and topology. In this work, we present novel second-kind integral equations for its solution which obviate the need for constructing a suitable parametrix to approximate the in-surface Green’s function. The resulting integral equations are well-conditioned and compatible with standard fast multipole methods and iterative linear algebraic solvers, as well as more modern fast direct solvers. Using layer-potential identities known as Calderón projectors, the Laplace-Beltrami operator can be pre-conditioned from the left and/or right to obtain second-kind integral equations. We demonstrate the accuracy and stability of the scheme in several numerical examples along surfaces described by curvilinear triangles.     

Additive schwarz methods for indefinite hypersingular integral equations in R3 - the p-version

We propose and analyze preconditioners for the p-version of the boundary element method in three dimensions. We consider indefinite hypersingular integral equations on surfaces and use quadrilateral elements for the boundary discretization. We use the GMRES method as iterative solver for the linear systems and prove for an overlapping additive Schwarz method that the number of iterations is bounded. This bound is independent of the polynomial degree of the ansatz functions and of the size of the underlying mesh. For a modified diagonal scaling, which uses special basis functions, we prove that the number of iterations grows only polylogarithmically in the polynomial degree. Here, a sufficiently fine mesh is required. Numerical results supporting the theory are presented.     

A bilateral asymptotic method of solving the integral equation of the contact problem of the torsion of an elastic half-space inhomogeneous in depth

An approximate semi-analytical method for solving integral equations generated by mixed problems of the theory of elasticity for inhomogeneous media is developed. An effective algorithm for constructing approximations of transforms of the kernels of integral equations by analytical expressions of a special type is proposed, and closed analytical solutions are presented. A comparative analysis of the approximation algorithms is given. The accuracy of the method is analysed using the example of the contact problem of the torsion of a medium with a non-uniform coating by a stiff circular punch. The relation between the error of the approximation of the transform of a kernel by special analytical expressions, constructed using different algorithms and the error of approximate solutions of the corresponding contact problems is investigated using a numerical experiment.     

Exponential convergence of the hp-version for the boundary element method on open surfaces

Summary. We analyze the boundary element Galerkin method for weakly singular and hypersingular integral equations of the first kind on open surfaces. We show that the hp-version of the Galerkin method with geometrically refined meshes converges exponentially fast for both integral equations. The proof of this fast convergence is based on the special structure of the solutions of the integral equations which possess specific singularities at the corners and the edges of the surface. We show that these singularities can be efficiently approximated by piecewise tensor products of splines of different degrees on geometrically graded meshes. Numerical experiments supporting these results are presented. Received December 19, 1996 / Revised version received September 24, 1997 / Published online August 19, 1999     

Note on the integral mean value method for Fredholm integral equations of the second kind

We study the paper of Avazzadeh et al. [Z. Avazzadeh, M. Heydari, G.B., Loghmani, Numerical solution of Fedholm integral equations of the second kind by using integral mean value theorem, Appl. Math. Model. 35 (2011) 2374–2383] with the integral mean value method for Fredholm integral equations of the second kind. The objective of the note is threefold. First, we point out a basic error in the paper. Second, we find that the given numerical examples are only related to the special cases of Fredholm integral equations of the second kind with the degenerate kernels, which can be solved simply. Third, due to the basic error, our observations reveal that generally the suggested method should not be considered for a Fredholm integral equation of the second kind.     

Potential-based numerical solution of Dirichlet problems for the Helmholtz equation

Three-dimensional Dirichlet problems for the Helmholtz equation are considered in generalized formulations. By applying single-layer potentials, they are reduced to Fredholm boundary integral equations of the first kind. The equations are discretized using a special averaging method for integral operators with weak singularities in the kernels. As a result, the integral equations are approximated by systems of linear algebraic equations with easy-to-compute coefficients, which are solved numerically by applying the generalized minimal residual method. A modification of the method is proposed that yields solutions in the spectra of interior Dirichlet problems and integral operators when the integral equations are not equivalent to the original differential problems and are not well-posed. Numerical results are presented for assessing the capabilities of the approach.