卷积位势的快速算法

FAST EVALUATION OF CONVOLUTION-TYPE NONLOCAL POTENTIAL

卷积位势广泛存在于科学和工程领域,它的高效高精度计算往往是数值仿真的瓶颈.卷积位势是典型的非局部积分,卷积核函数通常在原点或者无穷远处具有奇异性,密度函数是光滑速降函数并可能具有较强的各向异性.无论是从卷积还是从傅里叶积分出发,我们首先将全空间截断到有界矩形区域并将其等距离散,再应用傅里叶谱方法来高精度逼近密度函数.理想的求解器需要在保证高精度的同时,尽可能提高计算效率,并妥善处理各向异性密度函数的情形.本文详细回顾了目前流行的三类基于积分方程的高精度快速算法,包括基于非均匀快速傅里叶变换的算法、基于高斯和的算法与核截断算法.它们都能达到谱精度,计算效率都类似于离散快速傅里叶变换(FFT),并都能处理各向异性的密度函数.这三类算法具有离散卷积结构;一旦生成了离散张量,位势的计算将转化为两倍长度向量的傅里叶变换,计算效率达到了近似最优,且与各向异性强度无关.最后我们介绍了误差估计的已有结果,并用实例从精度、效率和各向异性等方面展示了算法能力.

Convolution-type nonlocal potentials are quite common and important in many science and engineering fields.Efficient and accurate evaluations of such potentials often bottleneck the real time simulations.The convolution kernel is usually singular or discontinuous at the origin and/or at the far field.The density is a smooth fast-decaying function,and is naturally well approximated by Fourier spectral method on a bounded rectangular domain,which is uniformly discretized in each spatial direction,with a nearly optimal complexity of O(N log N)that is inherited from the discrete Fast Fourier Transform.In some cases,there exists a strong spatial anisotropy in the density.Nonlocality,singularity and anisotropy are three challenges in convolution evaluation.The numerical problem is to compute the convolutions accurately and efficiently on such uniform mesh grid.In this article,we mainly review the state-of-art fast integral algorithms,including the NonUniform-FFT based method(NUFFT),Gaussian-Sum based method and Kernel Truncation method.All these methods achieve spectral accuracy with a FFT-like complexity O(N log N),and can be rewritten as a discrete convolution structure.The discrete convolution structure helps deal with strong anisotropy perfectly using a pair of FFT and inverse FFT(iFFT)on a twofold zero-padded density.Rigorous error estimates and extensive numerical results are shown to confirm the accuracy,efficiency and anisotropy performance.