Fast computation of the spectral differentiation by the fast multipole method. (1st July 2019) - Tian, Yan; Xiang, Shuhuang; Liu, Guidong
Abstract: This paper is concerned with the application of the fast multipole method (FMM) to the pseudospectral methods. The spectral differentiation in pseudospectral methods involves (dense) matrix–vector products, which, if evaluated directly, entail O ( N 2 ) operations. The core of this work lies in the fact that the FMM leads to a significant speed-up in CPU time with a major reduction in the amount of computer memory needed when performing matrix–vector products. The FMM is exploited to estimate the barycentric weights and the pseudospectral differentiation, which reduces the complexity to O ( N ) . Furthermore, we show the convergence analysis and present the applications to the second-order boundary value problems. Numerical examples confirm the advantages of the method.