Fast Numerical Methods Based On The Fast Multipole Method

In engineering calculations and many practical problem-solving scenarios,there are often large-scale calculation problems that need to be addressed.Direct calculations for these large-scale problems will incur huge computational costs.Additionally,for direct calculations,personal computers are often limited in handle small-scale calculations due to memory constraints.As one of the top ten algorithms of the 20 th century,the fast multipole method stands out for its ability to improve computational efficiency by reducing computational complexity.However,the conventional fast multipole method relies on the analytic structure of the kernel function,which limits its applicability to specific kernels.Therefore,efforts should be made to extend the method to more general kernels.Firstly,we present scientific problems that can be reduced to evaluating all pairwise interactions,followed by an overview of the development of the boundary element method.We also provide an analysis of the advantages of the boundary element method as compared to the finite element method.In order to improve computational efficiency for large-scale problems,it is necessary to study the fast multipole method.Next,we introduce the basic theory of the fast multipole method,and provide a historical development and current status of research on this method.Secondly,we present the fast multipole boundary element method(fast BEM)for solving the Fredholm integral equations of the second kind.The multipole expansion and local expansion of the fast multipole method are based on polynomial approximation of the kernel,which are well-defined and analytic in the far cells.The proposed algorithm efficiently extends the fast BEM to integral equations with more general kernels.Compared to the direct method,the computational costs can be significantly reduced,especially for large-scale problems requiring high accuracy.Additionally,in terms of computation time,the proposed method has a slight advantage over the analytic fast BEM.Thirdly,a kernel-independent uniform fast multipole method(UFMM)is presented for fast summation of particle interactions,where the kernel is approximated by using the Floater-Hormann(FH)rational interpolant at the equispaced grids.The proposed UFMM is stable and the accuracy can be improved as the number of nodes increases.Moreover,it allows for reducing the cost of the moment-to-local translation(M2L)operators dramatically accelerated by fast Fourier transform(FFT).In addition,a modified smooth-UFMM for some sufficiently smooth kernels is considered,which has better performance than the originally smooth-UFMM.The efficiency and accuracy are illustrated by numerical examples arising from the method of the regularized Stokeslets(MRS)and inverse quadratic kernels.Finally,to efficiently compute the two-dimensional discretized integral operator on the boundary,we introduce several methods based on the Unified Fast Multipole Method(UFMM).These include the UFMM constant,linear,and quadratic element methods,as well as their smooth versions.Compared to direct methods,these FMM-accelerated boundary element methods can significantly reduce the computational time for matrix-vector multiplication within the GMRES iterative process,particularly when dealing with large degrees of freedom in discrete systems.Moreover,these fast methods are kernel-independent,which means they can be applied to a wider range of kernel functions.The calculation of the M2 L operator in these algorithms can be accelerated by FFT.When dealing with two-dimensional singular boundary integrals,we use a subtraction singularity technique.Combining the subtraction singularity technique with the UFMM boundary element methods,the obtained methods can efficiently evaluate the boundary singular integral equations.The result fast algorithms are well suited to a wide range of problems.We demonstrate the effectiveness of our proposed methods through several examples.